[Python] 소수 판별, 소수 리스트 구하기 (feat.에라토스테네스의 체)

에라토스테네스의 체

수학에서 소수를 찾는 방법론 중 하나입니다.

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 제외되지 않은 3은 소수이다.
4. 자기 자신을 제외한 3의 배수를 모두 지운다.
5. 제외되지 않은 5는 소수이다.
6. 자기 자신을 제외한 5의 배수를 모두 지운다.
7. 제외되지 않은 7은 소수이다.
8. 자기 자신을 제외한 7의 배수를 모두 지운다.

위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

만약 120까지 수 중에서 소수를 구하고 싶다면, 11^2 > 120 이므로 11보다 작은 수들의 배수들만 지워도 소수를 구할 수 있습니다.

Python 코드

소수 리스트 구하기

에라토스테네스의 체를 이용하여 120이하의 소수 리스트를 구해보겠습니다.

이렇게 입력한 n 이하의 소수 리스트를 구할 수 있습니다.

만일 단일 n이 소수인지 판별하고 싶다면 해당 소수 리스트에서 sqrt(n) 이하의 소수로 나누었을 때 나누어지는 수가 없는지 확인하여 판별할 수 있습니다.

단일 소수 판별

간단하게 n만 소수인지 확인하고 싶다면 2이상 sqrt(n)이하의 수들로 n을 나누어보고 나누어지는 수가 없는지 확인하면 됩니다.

연속된 큰 수의 소수판별

n이 엄청나게 큰데다 연속해서 판별해야 한다면, 에라토스테네스의 체를 활용하여 sqrt(n) 이하의 소수 리스트를 구한 다음 활용하는 것이 더 빠를 수 있습니다.

아래는 소수 1141097을 판별하는 시간을 비교해 본 코드입니다.

def is_prime1(n):
    for num in range(2, int(n**1/2) + 1):
        if n % num == 0:
            return False
    return True


def prime_list(n):
    lst = [0] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if lst[i] == 0:
            for j in range(i+i, n, i):
                lst[j] = 1
    return [i for i in range(2, n) if lst[i] == 0]


def is_prime2(n):
    lst = prime_list(n)
    for num in lst:
        if n % num == 0:
            return False
    return True

 is_prime1(1141097)
 is_prime2(1141097)

1. is_prime1(n)을 활용하여 계산 할 경우 약 0.15초

2. is_prime2(n)을 활용하여 계산 할 경우 약 0.9 초, 이 중 0.88초는 prime_list(n)에서 소요

단일 소수판별은 is_prime1이 빠르지만 11401097, 1141093, 1141087 등과 같이 큰 소수를 10번이나 계산한다면

is_prime1은 0.15 * 10으로 약 1.5초가 됩니다.

만약 is_prime2를 prime_list(n)와 따로 계산하여 리스트를 먼저 구한다면 0.88 + 0.02 * 10으로 약 1초로 더 빠르게 됩니다.

더 많은 소수를 판별한다면 차이는 더 벌어지므로 큰 수를 여러번 판별해야 할 경우 에라토스테네스의 체를 활용하여 소수 리스트를 미리 구하는 것이 효율적입니다.