[프로그래머스] 소수 찾기 - JAVA

프로그래머스 소수 찾기 - JAVA

---

문제 설명

1. 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
2. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
   (1은 소수가 아닙니다.)

제한 조건

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

문제 풀이

1. n의 범위가 백만까지여서 검사 비용을 줄일 수 있는 에라스토테네스의 체를 사용한다.
2. n범위의 boolean배열을 생성 후 소수 유무를 저장.
3. 2부터 n까지 boolean배열을 검사 소수인 경우 값을 증가.

소스 코드

class Solution {
    public boolean[] isPrime;

    public int solution(int n) {
        isPrime = new boolean[n + 1];
        eratosthenes(n);

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

    public void eratosthenes(int n) {
        isPrime[0] = isPrime[1] = true;

        for (int i = 2; i * i <= n; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }
}