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

문제출처

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

코딩테스트 연습 - 소수 찾기

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] prime_checks = new boolean[n + 1]; //true : 소수 아님 false : 소수
        prime_checks[0] = true;
        prime_checks[1] = true;

        for(int i = 2; i * i <= n; i++){
            if(!prime_checks[i]){
                for(int j = i * i; j <= n; j += i){ 
                    prime_checks[j] = true;
                }
            }
        }
        for(boolean prime_check : prime_checks){
            if(!prime_check) {answer++;}
        }
        return answer;
    }
}

평소에 소수 구하는 방식으로 했더니 시간초과로 통과하지 못 해서 에라토스테네스의 체 개념을 알게 됐다.

기본적인 개념은

소수의 배수가 되는 수를 지워나가는 방식이다.

i * i를 기준으로 삼는 이유는

숫자 n이  p*q로 표현될 때 한 수는 항상 n^(1/2)이하, 다른 한 수는 n^(1/2) 이상이기 때문에 모든 수를 조사할 필요 없이 i*i <= n까지만 검사하면 된다.