[프로그래머스] Lv.0 합성수 찾기

class Solution {
    public int solution(int n) {
        int answer = 0;
    
        boolean array[] = new boolean[n+1];
        // 소수가 아니면 true로 바꾸기
        // 1은 소수가 아니므로 true
        array[1] = true;
        //에라토스테네스의 체로 구하기
        for(int i=2; i<=n; i++){
            if(!array[i]){
                for(int j=i*i; j<=n; j+=i) array[j] = true;
            }
        }
        for(int i=2; i<=n;i++){
            if(array[i]) answer++;
        }
        
        
        return answer;
    }
}

에라토스테네스의 체로 소수가 아닌 것들을 카운트해서 반환했다.

에라토스테네스의 체에 대해서는 알고리즘 탭에서 따로 정리하겠다.