Programmers_JAVA_소수_찾기(에라토스테네스의 체)

문제 설명

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

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

제한 조건

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

 

이 문제는 에라토스테네스의 체 알고리즘을 사용해야만 풀 수 있는 문제였다.

처음에는 2중 for문으로 평범하게 소수 찾는 알고리즘을 구현했는데, 시간 초과와 효율성 오류로 문제가 통과되지 않았다.

에라토스테네스의 체 알고리즘은 특정 문제에 해당하지 않는 경우의 수를 탐색 직전에 차단시키는 방법이다.

소수를 찾았을 때, 해당하는 소수들의 배수들을 전부 1로 초기화하고 값이 1일때는 해당 for문을 수행하지 않는 방법이다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] numbers = new int[n+1];
        for (int i = 0; i <= n; i++) numbers[i] = i;

        //2부터 n 전까지 순회.
        for (int i = 2; i <= n; i++) {
            //인덱스 i의값이 1이면 건너 뜀.
            if (numbers[i] == 1) continue;
            answer++;
            //x가 소수였을 경우, x의 배수들을 전부 1로 초기화. 
            //에라토스테네스의 체 알고리즘의 핵심. (채로 거른다)
            for (int j = 2 * i; j <= n; j += i) numbers[j] = 1;
        }
        return answer;
    }
}