합성수 찾기

이 문제에 사용되는 알고리즘

Chat-GPT의 코드 ( 에라토스테네스의 체 알고리즘 ) ( 시간복잡도 : O(n log log n) )

class Solution {
    public int solution(int n) {
        // isPrime[i]는 i가 소수이면 true, 합성수이면 false를 저장하는 배열입니다.
        boolean[] isPrime = new boolean[n+1];
        // 2부터 n까지 모든 수를 소수로 초기화합니다.
        for(int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        
        // 에라토스테네스의 체 알고리즘을 이용하여 소수를 찾습니다.
        for(int i = 2; i*i <= n; i++) {
            // i가 소수인 경우, i의 배수들을 합성수로 체크합니다.
            if(isPrime[i]) {
                for(int j = i*i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // 합성수의 개수를 세기 위한 변수입니다.
        int count = 0;
        // 4부터 n까지 돌면서, 합성수를 찾습니다.
        for(int i = 4; i <= n; i++) {
            // i가 소수가 아닌 경우, i는 합성수입니다.
            if(!isPrime[i]) {
                count++;
            }
        }
        // 합성수의 개수를 반환합니다.
        return count;
    }
}

나의 코드 ( 시간복잡도 : O(N²) )

class Solution {
    public int solution(int n) {
        int count = 0;
        int hs = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) {
                    count++;
                    if (count >= 3) {
                        hs++;
                        count = 0;
                        break;
                    }
                }
                if (i == j) {
                    count = 0;
                }
            }
        }
        return hs;
    }
}