[프로그래머스] 소수 찾기 자바 에라스토테네스의 체

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

문제

1 ~ n 까지의 범위에서 소수의 갯수를 구하시오.

접근

1.기존에 사용했던 소수인지 체크하는 메서드를 활용하여 소수면 answer ++ 한다.

public int solution(int n) {
        int answer = 0;
        for(int i = 1; i <= n; i ++){
            if(checkPrimeNumber(i)) answer ++;
        }
        return answer;
    }

    //소수체크
    public boolean checkPrimeNumber(int num) {
        int cnt = 0;
        for (int i = 1; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                cnt ++;
                if (i != num / i) { // 중복 제거 (예: 5x3, 3x5)
                    cnt ++;
                }
            }
        }

        return cnt == 2;
    }

발견된 문제

n이 커질수록 매우 느려짐. 시간초과
제안 : 에라스토테네스의 체 법칙 활용. ( i의 모든 배수는 i를 약수로 가진다.)

수정

public int solution2(int n) {
        if(n < 2) return 0;
        boolean[] prime = new boolean[n + 1]; // 1 ~ n까지 true false
        Arrays.fill(prime, true);
        prime[0] = false; //0과 1은 소수가 아니므로 false
        prime[1] = false;

        // 2 ~ 각 수의 제곱들은 false로 처리해야한다. (에라스토테네스의 체 응용)
        for(int i = 2; i * i <= n; i ++){
            if(prime[i]){
                for(int j = i * i; j <= n; j += i){ // i^2 부터 +i 들은 소수가 아님.
                    prime[j] = false;
                }
            }
        }
        int answer = 0;
        for( int i = 2; i <= n; i ++){
            if(prime[i]) answer ++;
        }

        return answer;
    }

개선된 버전

에라스토테네스 체 방식보다 빠른 방법이 있다고 하여 기록한다.

public int solution3(int n) {
        if (n < 2) return 0;

        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        // 짝수 처리 (2 제외)
        for (int i = 4; i <= n; i += 2) {
            isPrime[i] = false;
        }

        // 홀수만 검사
        for (int i = 3; i * i <= n; i += 2) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += 2 * i) {
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) count++;
        }

        return count;
    }