오일러 프로젝트 07

오일러 프로젝트 7번문제는 10001번째 소수를 찾는 문제이다.

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, … 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요.(http://euler.synap.co.kr/prob_detail.php?id=7)

오일러 프로젝트에서 처음으로 소수 판별 함수를 작성해볼 차례이다. 소수 판별 함수는 사실 알고리듬 자체는 매우 단순한데, 문제는 성능이다. 나이브하게 작성한 코드는 매우 느릴 수 밖에 없다.

1. 2보다 작은 수는 0, 1 외에 음수이므로 이들은 모두 소수가 아니다.
2. 2는 소수이다.
3. 2보다 큰 경우 2, 3, 4… 등 자기 자신보다 작은 수로 나눠서 한 번이라도 나눠지면 소수가 아니다.
4. 그 외에는 소수이다.

가장 간단하게 위의 내용 대로 소수 판별 함수를 구현하면 아래와 같다. 물론 불행히도 이는 별로 좋은 성능의 코드가 아니다.

def isPrime(num):
    if num < 2 :
        return False
    if num == 2:
        return True
    k = 2
    while k < num:
        if num % k == 0:
            return False
        k += 1
    return True
def doit():
    primes = []
    a = 2
    while len(primes) < 10001:
        if isPrime(a):
            primes.append(a)
        a += 1
    print(primes[-1])
# 104743
# CPU times: user 1min 40s, sys: 183 ms, total: 1min 40s
# Wall time: 1min 40s

알고리듬 개선

소수 판별 함수의 알고리듬을 개선해보자. 소수 판별 알고리듬은 기본적으로 루프를 돌면서 나눠보는 것이고, 이 문제에서는 10,001 번째 소수를 찾을 때까지 루프에 루프를 계속 돌아야한다. 따라서 루프를 도는 횟수와 길이를 줄일 수 있다면 성능을 제법 개선할 수 있다.

1. 2를 제외한 모든 짝수는 소수가 아니므로 미리 걸러낼 수 있다. (따라서 절반의 케이스를 여기서 줄일 수 있다.)
2. 3의 배수들 역시 같은 방법으로 미리 걸러낼 수 있다. (N이 크다면 의미가 있을 수 있다.)
3. N이 소수가 아닌 경우 가 되는데, 따라서 p로 나누어 떨어지면 자동으로 q로 나누어 떨어진다. 이 때 p가 가장 커질 수 있는 한계는 p = q 일 때 이므로, N의 제곱근까지 나눠봤을 때 나눠지는 수를 찾지 못했다면, N의 제곱근 이후부터는 나눠지는 수를 찾을 수 없게 된다. N이 크면 클 수록 검삭해야하는 한계를 줄일 수 있어서 속도 개선에 가장 중요한 로직이다.

그래서 여러 개선을 거쳐 다음과 같은 코드로 변경해보겠다. 처리함수에서도 짝수나 3의 배수를 피하는 식으로 비교의 횟수를 대폭 줄였다. n을 늘려가면서 등장한 소수의 개수를 세는데, 이 역시 5와 7부터 시작하여 짝수와 3의 배수를 배제해나가면서 카운트하면 조금이라도 성능을 높일 수 있다.

def isPrime(num):
    if num < 2:
        return False
    if num is 2  or num is 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if num < 9:
        return True # 5, 7
    k = 5
    l = num**0.5
    while k <= l:
        if num % k == 0 or num % (k+2) == 0:
            return False
        k += 6
    return True
def main():
    primes = [2, 3]
    n = 5
    while len(primes) < 10001:
        if isPrime(n):
            primes.append(n)
        if isPrime(n+2):
            primes.append(n+2)
    n += 6
    print(primes[10000])
%time main()
# 104743
# CPU times: user 362 ms, sys: 46 µs, total: 362 ms
# Wall time: 360 ms

특정한 범위내에서의 소수의 목록을 구하는데는 소수 판별함수를 쓰는 것 보다, 에라토스테네스의 체를 이용하는 것이 더 빠른데, 이는 다음에 해당 패턴의 문제에서 살펴보도록 하겠다.