소수 (솟수)

문제 1. 어떤 수 N (=upperbound) 보다 작은 소수 목록(prime numbers)을 구하라.

소수는 1과 자기 자신만을 약수로 갖는 수이다. 그러므로 무언가의 2배, 3배, 4배 등이 되는 수라면 이는 소수가 아니다. N=60이라고 하면, 그보다 작은 소수들은 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59] 가 있을 것이다. 이를 구하는 가장 효율적인 방법은 기원전에 발견되었다(에라토스테네스의 체, Sieve of Eratosthenes). 이 방법은 우선 모든 수를 소수라고 추정한 뒤, 어떤 소수의 배수처럼 소수가 아닌 수를 지워나가는 것이다.

• 먼저 0, 1은 소수가 아니라고 정의한다.
• 최초의 소수인 2를 primes에 추가한 다음, 그것의 배수(2*2, 3*2, 4*2, 5*2, ...) 를 소수가 아니라고 표시한다(지울 수들이 N이 되기 전에 멈춤). 이것이 '체'로 거르는 과정이다.
• 앞서 걸러지지 않은 그 다음 수들(3, 5, ...) 에 대해서도 이를 반복한다.

여기서 우리가 알아야 할 지식은, 0, 1은 소수가 아니며, 2는 소수라는 것 정도이다. 왜냐면, 2는 가장 작은 소수로서 이것의 배수는 이미 소수가 아닌 것으로 촘촘히 걸러졌을 것이기에, 그 다음에 나타나는 '걸러지지 않은 수'가 소수라고 추정된 것은 적절하다고 보는 것이다. 예를 들어, 3을 보자면 이는 앞선 2의 배수의 체(거름망)에서 소수라고 걸러지지 않았기에 이것은 소수라고 본다.

그 다음 적용되는 3의 배수라는 체는 2보다는 더 성긴 체라고 할 수 있다. 그 다음 나타나는 4는 2의 배수라는 체에서 소수가 아니라고 걸러져 버렸기에 굳이 거름망으로 선택하지 않는다. 다음엔 5로 갈 수 있으니 이것은 소수의 목록에 추가하고, 그 배수들은 소수가 아니므로 체로 걸러낸다. 이를 반복한다.

# sieve_prime.py

is_prime = []
upperbound = int(input('Give prime upper bound: '))
sieve_size = upperbound + 1
primes = []

is_prime = [True] * sieve_size
is_prime[0] = is_prime[1] = False
for i in range(2, sieve_size):
    if not is_prime[i]: continue
    for j in range(2*i, sieve_size, i):  # can 2*i be improved as i*i
        is_prime[j] = False
    primes.append(i)

print(primes)

'''
python sieve_prime.py
Give prime upper bound: 60
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]

python sieve_prime.py
Give prime upper bound: 59
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
'''

여기서 체의 크기(sieve_size)는 최초에 0을 index 0에 추가해 주었기 때문에 1만큼 더 크게 설정했다. 첫번째 for loop은 2부터 N까지 숫자를 증가하면서, 먼저 그 수가 소수가 아니라면 체로 사용하지 않는다. 만일 그 수가 소수라면 그 배수들을 체로 걸러 합성수(소수가 아닌 수)라고 표시한다(is_prime[j] = False). 이 때 어떤 소수의 배수를 체로 이용해 수를 거르는 과정이 두번째 for loop이다. 이 때, 주석에 표시한 것 처럼, 2*i, 3*i, ... 를 체로 사용하는게 아니라, i*i, i*i+i = i(i+1), i(i+2), ... 를 체로 사용하면 계산 수를 줄일 수 있다. 그 이유를 문자로 분석하기 보다는 실제 계산과정도 모사해 볼 겸 아래처럼 살펴보자.

• 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, ...
• 3, 6, 9, 12, 15, 18, 21, ...
• 5, 10, 15, 20, 25, ...

i = 5를 보면, i*i = 25 이전의 숫자들은 이미 이전 체에서 걸러져 버린 것을 볼 수 있다(10, 15, 20 처럼 이탤릭체로 표시).