프로그래머스 소수 찾기 [Java]

프로그래머스 Level 1 소수 찾기 (자바)소수 찾기

 

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한사항

• n은 2이상 1000000이하의 자연수입니다.

 

 

입출력 예

입출력 예

한 줄 요약

1부터 n까지 소수 구하기! 에라토스테네스의 체를 활용해야 한다.

 

* 에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

내 코드

1. 주어진 정수(n) + 1 크기의 boolean형 배열 distinct를 만든다.(정수와 배열 순서를 맞추기 위함)

2. distinct[2 ~ n]까지 모두 true로 변환한다.

3. 정수형 변수 num에 n의 제곱근을 넣어준다.

4. distinct[2 ~ n]까지에서 true일 때,

    i ~ i*j까지 범위에서 distinct[i*j]를 false로 반환한다.

   (에라토스테네스의 체를 활용한 것으로, 첫 시작수를 제외한 배수는 모두 소수가 아닌 것을 표현)

5. distinct[] 배열에서 true인 것만 수를 세 반환한다.

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        boolean[] distinct = new boolean[n+1];
        
        for (int i=2; i<=n; i++) {
            distinct[i] = true;
        }
        
        int num = (int)Math.sqrt(n);
        
        for (int i=2; i<=num; i++) {
            if (distinct[i] == true) {
                for (int j=i; j*i<=n; j++) {
                    distinct[i*j] = false;
                }
            }
        }
        
        for (int i=2; i<=n; i++) {
            if (distinct[i] == true) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

주어진 정수 n+1 크기의 배열을 선언하는 것과 에라토스테네스의 체를 활용하는 것이 핵심!