[알고리즘] 소수 판정법 - 에라토스테네스의 체

에라토스테네스의 체란?

 

고대 그리스 수학자 에라토스테네스가 만든 소수 판정법.

임의의 자연수 $N$에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법.

 

우선 에라토스테네스의 체를 쓰지 않고 그냥 소수를 구해보자

 

bool isPrime = true;
int N;

for(int i=2;i<N;i++){
	if(N%i == 0) isPrime = false;
}   

return isPrime;

 

2부터 $N$미만의 수들을 모두 $N$과 나눠서 만약 나머지가 0인 경우가 있으면 소수가 아니다. 이런 식으로 판별하는 방식은 모든 2부터 $N$미만의 모든 수들을 전부 나눠줘야하므로 시간복잡도가 너무 높아진다.

 

이럴 때 조금 더 나은 알고리즘은 2부터 $\sqrt{N}$까지의 수들을 위의 알고리즘과 같이 탐색하는 방식이다. 

이 방식은 불필요한 계산들을 안 해도 된다는 장점이 있다. 하지만 범위 내의 모든 수들을 소수 판정하는데에는 비효율적이다. 

 

에라토스테네스의 체 (Sieve of Eratosthenes)

 

2부터 어떤 수 $N$까지 자기 자신을 제외한 배수들을 표에서 지워나가면서 소수를 구하는 방식이다.

예시를 보자.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

1에서 25까지의 수들 중에 소수인 수들을 구해보자.

 

우선 1은 소수가 아니므로 지워준다.

 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

2를 제외한 2의 배수들을 지워준다.

 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

 

3을 제외한 3의 배수들을 지워준다.

 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

5를 제외한 5의 배수들을 지워준다

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

이렇게 지워지지 않은 수들, (2, 3, 5, 7, 11, 13, 7, 19, 23)

1에서 25사이의 소수들을 에라토스테네스의 체로 구해보았다.

 

 

이 알고리즘을 코드로 구현해보자

 

void Eratosthenes(int n){

	if(n<=1) return;
    
    int prime[n+1];
	
    // 2에서 N까지 배열 인덱스와 같은 수를 입력해준다.
	for(int i=2;i<=N;i++){
    	prime[i] = i;
    } 
    
    
    for(int i=2;i*i<=N;i++){
    	//배열값이 0이면 넘긴다.
    	if(v[i] == 0) continue;
        
        //자기자신을 제외한 i의 배수들을 전부 지워준다.
        for(int j=i*i;j<=N;j+=i){
        	v[j] = 0;
        }
	}
    
}

 

https://kimmessi.tistory.com/151

[에라토스테네스의 체] BOJ 1990 소수인팰린드롬

 

https://kimmessi.tistory.com/119

[에라토스테네스의 체] BOJ 16563 어려운 소인수분해

 

위의 문제들은 에라토스테네스를 활용해 푸는 문제들이다.