소수 구하기

소수 구하기

에라토스테네스의 체

어떠한 수의 배수는 소수가 아니므로 범위 내에서 소수가 아닌 수를 제외하는 방식

마치 체를 통과시키듯이, 소수가 아닌 수를 순차적으로 제외

 

    public static int solution(int n) {
        int intArray[] = new int[n];

        // 0, 1 제외
        for (int i = 2; i < n; i++) {
            intArray[i] = 1;
        }

        // n의 제곱근까지
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (intArray[i] == 0) continue;

            int num = i * 2;
            while (num < n) {
                intArray[num] = 0;
                num += i;
            }
        }

        return Arrays.stream(intArray).sum();
    }

먼저 0, 1은 소수가 아니기 때문에 2부터 n까지 소수라고 체크하기 위한 1로 설정해줍니다.

n-1까지 수의 소수를 구한다면 Math.sqrt(n-1)이 정확한 방법입니다.

 

n의 제곱근까지만 수행하면 그 뒤는 더 이상 수행할 필요가 없다. 따라서 반복문의 최대는 n의 제곱근까지 진행하며

이미 소수가 아닌 0으로 처리된 경우에는 진행하지 않고 다음 수로 진행합니다.

 

처음 수는 i = 2, num = 4이며 4부터 하나씩 소수가 아닌 0으로 처리해주며 4, 6, 8, 10, 12 ... 순서로 진행됩니다.

그 다음은 i = 3이며, num = 6, 9, 12, 15 순으로 증가되며 하나씩 소수가 아닌 수를 제외해줍니다.

마지막은 배열안에서 소수인 경우 1로 처리하며

소수가 아닌 경우 0으로 처리되었기 때문에 배열의 모든 값을 더해주면 소수의 개수가 나오게 됩니다.