[알고리즘] 소수 구하기 - 에라토스테네스의 체 Sieve of Eratosthenes

 

에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘 : 

고대 그리스 수학자 에라토스테네스가 발견한 방법으로 소수를 찾는 알고리즘

체로 치듯이 숫자를 걸러내는 방식. 소수의 배수를 모두 지우면 나머지는 소수가 된다

 

ex ) 2 ~ 120 사이의 소수를 구하는 방법

   

출처 : 위키백과

   1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 
   2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 
   3. 자기 자신을 제외한 2의 배수를 모두 지운다. 
   4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 
   5. 자기 자신을 제외한 3의 배수를 모두 지운다. 
   6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 
   7. 자기 자신을 제외한 5의 배수를 모두 지운다. 
   8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 
   9. 자기 자신을 제외한 7의 배수를 모두 지운다. 
   10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11^2>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.

즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

에라토스테네스의 체는 대량의 숫자들을 소수 판별할 때는 매우 효율적이지만

특정 숫자에 대한 소수 판별에는 비효율적이다.

 

 

메서드 eratosthenes() : 2~ num 까지의 수를 소수 판별

매개변수 : int num

반환값 : num+1 크기의 배열 안에 인덱스가 소수일 경우 true, 소수가 아닐 경우 false를 담아 반환

boolean[] eratosthenes(int num) {
	boolean[] prime = new boolean[num+1];
	prime[0] = prime[1] = false;
    
    for(int i = 2; i <= num; i++) {
    	prime[i] = true;
    }
    
    for(int i = 2; i*i <= num; i++) {
    	for(int j = 2 * i; j <= num; j += i) {
    		prime[j] = false;
    	}
    } 
    return prime;
}

 

 

 

 

에라토스테네스의 체 Sieve of Eratosthenes : O(Nlog(logN))