[프로그래머스 Level 1] 소수 찾기 문제 풀이

❓ 문제

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

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

제한 조건

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

🖨️ 입출력 예

에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 11^2>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

진행방식?

1. 1차원 배열 생성 (n+1 크기)
2. 2부터 배수들을 모두 체크 (단, 자신은 제외하고 4,6,8,10..... <= n)
3. 다음으로 3의 배수들을 모두 체크
4. 4는 아선 2의 배수로써 체크가 되어 소수가 아니기 때문에 PASS
5. ,,,

💡 풀이

class Solution {

    public int solution(int n) {
        int answer = 0;
        // 에라토스테네스의 체로 거르기 위한 배열
        boolean[] flag = new boolean[n + 1];

        // 2부터 n까지의 수들을 지나며
        int i = 1;
        while(1 < ++i && i < n) {

            // 이미 걸러진 수(소수의 배수)는 PASS
            if(flag[i])
                continue;
            
            // 소수의 배수를 체크
            for(int j = i + i; j <= n; j += i)
                flag[j] = true;

        }

        // 걸러지지 않은 수의 개수 구하기
        for(int idx = 2; idx <= n; idx++) {
             if(!flag[idx])
                 answer++;
        }

        return answer;
    }

}

✏️ comment

첨에 효율성 테스트에서 우수수 다 탈락해서 당황,,
소수를 찾을 땐 에라토스테네스의 체를 이용하자 !