소수 찾기, 에라토스테네스의 체 | 프로그래머스

문제

✨ 문제 바로가기

문제	레벨	정답률
소수 찾기	Lv.1	63%

My Code

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i = 2; i<=n; i++){
            boolean tf = true;
            for(int j = 2; j < i; j++){
                if(i % j == 0){
                    tf = false;
                    break;
                }
            }
            
            if(tf == true){
                answer++;
            }
        }
        
        return answer;
    }
}

결과 - 일부 테스트 시간 초과 발생 🚨

우선 나는 2부터 n까지 돌면서, 2~n-1까지를 나눠서 떨어지는게 있다면 소수가 아니라는 뜻이니 boolean 변수를 false로 만들고 break 걸어주는 방식으로 풀었다.
그런데 이렇게 하면 일부 케이스에서 시간 초과가 발생해서 통과가 불가능 ,,

에라토스테네스의 체

-> 소수 구할 때 효율적인 알고리즘

1. 2부터 n까지 모든 수 배열에 저장
2. 배열에 남아있는 수 중 가장 작은 수를 소수로 판단
   그 배수를 모두 제거
3. 제거되지 않은 수들 = 소수!

class Solution {
    public int solution(int n) {
        // n까지의 소수의 개수를 세기 위해 배열을 선언 (true는 소수임을 나타냄)
        boolean[] isPrime = new boolean[n + 1];
        
        // 초기에는 모든 수를 소수로 간주
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        
        // 에라토스테네스의 체 알고리즘 적용
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // i의 배수를 모두 소수가 아닌 것으로 처리
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // 소수의 개수를 셈
        int answer = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                answer++;
            }
        }
        
        return answer;
    }
}

내가 초기에 생각한 방식과 완전 반대의 방식이다.
나는 처음부터 계산을 해보면서 소수인지를 판단했다면,
이 알고리즘에서는 애초에 소수로 가정하고 그 배수들을 제거해나가는 방식으로 좁혀나갔다.