[JAVA] 에라토스테네스의 체 (leetcode 204번)

leetcode 204번 문제

소수의 개수를 구하는 문제를 해결하는 도중

time limit exceeded라는 에러를 맞닥뜨렸다.

 

찾아보니 해당 에러는 소수를 찾는 알고리즘 '에라토스테네스의 체'를 이용해 해결할 수 있는 문제였다.

 

에라토스테네스의 체란?

소수를 판별하는 알고리즘으로, 대량의 소수들을 빠르고 정확하게 구하는 방법이다.

정수 x가 소수인지 아닌지를 판별하기 위해 추가적인 배열을 만드는 전처리 방식의 알고리즘 이다.

 

원리?

배열을 arr[]이라 하고, 

arr[] = 0 인경우 소수이고, arr[] = 1 인경우 소수가 아닌 것을 의미한다.

 

"소수가 되는 수의 배수를 지우면 남은 건 소수가 된다"라고 생각하는 알고리즘입니다.

소수가 무엇인지 찾을 필요가 없으며 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.

 

 

<위키백과 참고>

1. 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2. 소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 위 과정을 반복한다.

해당 원리를 적용하여 

리트 코드 204번 문제를 다시 풀어보았다. 

 

 

class Solution {
    public int countPrimes(int n) {
        boolean prime[] = new boolean[5000000];
         int answer=0;

        // 구하고자 하는 숫자 범위
       

        // 소수 = false
        // 0과 1은 소수가 아니므로 true
        prime[0] = prime[1] = true;

        for(int i=2; i*i<=n; i++){
        	// prime[i]가 소수라면
            if(!prime[i]){
            	// prime[j] 소수가 아닌 표시
            	for(int j=i*i; j<n; j+=i) prime[j]=true;                
            }        
        }    
        
        // 소수 출력
        for(int i=1; i<n;i++){
        	if(!prime[i]) answer++;    
        }

         return answer;
    }
}

 

 

 

 

그 결과는 성공!