[programmers] 소수 찾기 - Java

소수 찾기

문제 설명

제한 조건

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

입출력 예

입출력 예 설명

solution.java

class Solution {
    public int solution(int n) {
        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]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

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

        return count;
    }
}

핵심 키워드

• 해당 문제는 에라토스테네스의 체 알고리즘을 통해 해결할 수 있다.
• 에라토스테네스의 체 알고리즘은 소수를 판별하는 알고리즘이다.
• 어떤 수가 소수인지를 확인 할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다.
• 숫자 2부터 시작해서 모든 숫자를 1씩 증가하며, 해당 수의 배수는 소수가 될 수 없음을 표시한다.
• 검사할 수의 제곱이 검사할 범위를 넘어서지 않는다면, 반복을 계속한다.

결론!