합성수 찾기 (자바, Java)

합성수 = 소수가 아닌 수다. 소수는 1과 자기자신, 즉 2개만 약수로 가진 자연수이고, 3개 이상이면 소수가 아니란 소리.

1은 소수는 아니지만, 약수의 갯수가 1개이므로 합성수도 아니다. 따라서 소수구하는 알고리즘에, 반대값을 count해주면 된다.

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i=1; i<=n; i++) {
        	if (prime(n)[i]) {
        		answer++;
        	}
        }
        return answer;
    }
    
    // 에라토스테네스의 체, 소수가 아니면 true를 반환.
    public boolean[] prime(int n) {
    	boolean[] pn = new boolean[n+1];
    	
    	for (int i=2; i<n+1; i++) {
    			if (pn[i]) {
    				continue;
    			} else {
    				for (int j=i*i; j<=n; j+=i) {
    						pn[j] = true;
    				}
    			}
    	}
    	return pn;
    }
}