JAVA - 1부터 n사이에 소수의 개수 구하기

 

▼ 기존 작성 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=2; i<=n; i++){
            int cnt = 0;
            for(int j=1; j<=i; j++){
                if(i % j == 0) cnt ++;
                if(cnt > 2) break;
            }
            if(cnt == 2) answer++;
        }

        return answer;
    }
}

 

위 코드로 실행하였을때, 코드 자체는 성공하였으나 시간복잡도가 높아 통과되지 않는 케이스가 발생하였다.

 

 

▼ 수정된 코드

import java.util.*;

class Solution {
    public int solution(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // i의 배수는 소수가 아님
                }
            }
        }

        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) {
                count++;
            }
        }

        return count;
    }
}

 

위 코드는 에라토스테네스의 체 알고리즘을 보고 작성한 코드이다.

해당 코드로 수정했을때 시간복잡도가 해결되어 모든 테스트 케이스에 통과할 수 있었다.

 

***************************************************************************************************************

에라토스테네스의 체 알고리즘 이란?

 

고대 그리스 수학자 에라토스테네스가 발견한 제곱근을 이용한 소수를 구하는 방법.

소수를 구하는 최적의 알고리즘이라고 합니다.

 

소수는 n의 배수가 아니고 입력받은 수를 그 수보다 작은 수들로 나누어서 떨어지면 소수가 아니다.

그러므로, 모두 나누어 볼 필요없이 n 제곱근 까지만 나누어서 떨어지면 소수가 아니다.

***************************************************************************************************************