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

https://school.programmers.co.kr/learn/courses/30/lessons/120846

프로그래머스

문제

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

풀이

1부터 n까지의 수 중에 합성수의 개수를 return 하는 문제이다.

 

필자는 배열을 사용하여 1 ~ n 사이의 수를 소수와 합성수로 구분한 뒤, 해당 배열에서 합성수의 개수를 구해보았다.

for(int i = 2; i <= n / 2; i++) {
    if(!prime[i]) { // 만약 i가 소수라면
        for(int j = i * 2; j <= n; j += i) {
            prime[j] = true; // i의 배수인 j는 합성수이다.
        }
    }
}

물론 소수의 배수만 합성수인 것은 아니다.

합성수의 배수도 당연히 합성수이지만, 이미 소수의 배수를 걸러내는 과정에서 처리가 되었기 때문에 불필요한 과정을 생략해 주었다. (ex : 2의 배수를 합성수 처리하면 4의 배수는 자연스럽게 합성수(true)가 됨)

 

또한 반복문의 범위를 n / 2로 설정한 것은, n / 2까지 반복문을 돌리면 n까지 합성수인지 아닌지 판별이 가능하기 때문이다.

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        boolean[] prime = new boolean[n + 1];
        
        for(int i = 2; i <= n / 2; i++) {
            if(!prime[i]) {
                for(int j = i * 2; j <= n; j += i) {
                    prime[j] = true;
                }
            }
        }
        
        for(int i = 2; i <= n; i++) {
            if(prime[i]) answer++;
        }
        
        return answer;
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!