(프로그래머 코딩 테스트) 합성수 찾기(자바)

문제 설명

약수가 3개 이상인 수를 합성수라고 합니다.

자연수 n이 매개변수로 주어졌을 때, n보다 작거나 같은 합성수의 개수를 반환하도록 풀이 함수를 완성하십시오.

제한

• 1 <= n <= 100

I/O 예시

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 문에서 응답이 증가하는 조건입니다.

‘arr(i) == 1’에서 ‘arr(i) == 0’으로 변경되었습니다.

소수의 경우 arr(i) == 1이고 합성수의 경우 ‘arr(i) == 0’입니다.

자세한 설명과 설명은 이전 게시물에 있습니다.

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

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