소수 구하기 - 에라토스테네스의 체

소수를 구하는 방법은 여러가지가 있지만, 프로그램으로 구현할 때에는

 

시간복잡도를 고려하게 된다.

 

프로그램의 성능을 좌지우지하는 시간복잡도가 다른방법들에 비해 낮은 편이기 때문에

 

에라토스테네스의 체를 이용해 소수를 구하도록 한다.

 

방법은 아래와 같다.

 

1. 2부터 구하고자 하는 수 n까지의 자연수를 나열한다.

 

2. 소수인 2를 남기고 n까지의 모든 2의 배수를 제거한다. 2의 배수는 2라는 약수가 있기 때문에 소수가 아니기 때문이다.

 

3. 다음 수인 3은 이전 단계에서 제거되지 않았기 때문에 소수이다. 또한 3의 배수는 모두 소수가 아니기 때문에 n까지의 3의 배수들을 모두 제거한다.

 

4. 2번 단계에서 4는 제거되고 없기 때문에 5가 다음 소수이다. 또한 5의 배수는 모두 소수가 아니기 때문에 n까지의 5의 배수들을 모두 제거한다.

 

5. 같은 과정을 n까지 반복하고 나면 소수만 남게 된다.

 

기본 원리는 이렇다. 그런데 2부터 모든 2의 배수를 지우고, 또 3부터 모든 3의 배수를 지우는 것은 불필요한 중복된 작업을 포함한다.

 

정수 i의 배수를 지울 차례가 되었을때, i부터가 아닌 ixi부터 지우면 된다. 

 

왜일까?

 

예로 5의 경우를 들어보자.

 

5x5부터 시작해 모든 5의 배수는 이전 단계에서 다 지워졌을 수도 있고, 아직 지워지지 않은 수가 있을 수도 있다.

 

하지만 5x5 이전 5의 배수들은 5x4 (4의 배수), 5x3 (3의 배수), 5x2 (2의 배수)로 이미 이전 단계에서 다 지워졌다.

 

그렇다면 우리는 각 단계마다 ixi부터 시작함으로써 불필요한 작업을 줄일 수 있다.

 

하지만 프로그램을 이렇게 짤 경우, i가 무지막지하게 큰 숫자일 때 ixi는 프로그램 내에서 처리할 수 있는 범위를 초과해 이상한 결과가 나올 수 있기 때문에 ix2 또는 i+i정도로 해준다.

 

또한, 소수가 아닌 수들을 지울 때 실제로 수를 지우면 시간이 오래걸리니 bool 배열을 만들어 True, False로 지운척 표시만 해준다.

 

아래는 파이썬으로 구현한 코드이다.

 

MAX = 1000000
check = [False]*(MAX+1)
check[0] = check[1] = True
 
for i in range(2, MAX+1):
    if not check[i]:
        for j in range(i+i, MAX+1, i):
            check[j] = True

37이 소수인지 궁금하다면 check[37]을 확인하면 된다.

 

여기서는 False일 때 소수이다.