[프로그래머스 코딩테스트] 합성수 찾기(Java)

  문제 설명

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

 

  제한사항

• 1 <= n <= 100

 

  입출력 예

n	result
10	5
15	8

class Solution {
    public int solution(int n) {
        int[] arr = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            arr[i] = 1;
        }
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            if (arr[i] == 0) {
                continue;
            }
            int num = i * 2;
            while (num <= n) {
                 arr[num] = 0;
                 num += i;
            }
        }
        int answer = 0;
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] == 0) {
                answer++;
            }
        }
        return answer;
    }
}

  소수를 찾는 문제와 동일합니다. 마찬가지로 에라토스테네스의 체 방법을 이용했습니다. 그러나 마지막 for문에 answer가 증가하는 조건만 다릅니다. 'arr[i] == 1'에서 'arr[i] == 0'으로 변경했습니다. 소수의 경우 arr[i] == 1이고, 합성수의 경우 'arr[i] == 0'이 되는 원리를 이용하는 것입니다. 자세한 풀이와 설명은 이전 게시글에 있습니다.

 

에라토스테네스의 체 방법을 이용하는 알고리즘 설명이 궁금하다면

[프로그래머스 코딩테스트] 소수 찾기(Java) https://sigfriede.tistory.com/114