파이썬으로 소수(prime) 찾기

소수(素數, prime number)는 1과 자기 자신만을 약수로 가지는 1 이외의 정수입니다. 

 

정의를 따라 코딩해 보면 다음과 같죠. 

def is_prime1(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

그런데 약수는 대칭적입니다. 

 

약수의 개수가 짝수인 경우

1*6 = 6
2*3 = 6 
-------
3*2 = 6
6*1 = 6

6을 예로 들자면
약수가 1 2 3 6 이렇게 4개이고 
이 경우 2까지만 체크해도
소수인지 아닌지 알 수 있습니다.
정확하게는 6의 제곱근인 2.4494 이하까지만 체크하면 됩니다. 

 

약수의 개수가 홀수인 경우

1*4 = 4
2*2 = 4 
4*1 = 4

4에서는 마찬가지로 4의 제곱근인 2 이하까지 체크해야 합니다. 

 

'4 ** .5 = 2'이므로
'4 ** .5 + 1 = 3'이어야
'range(3) = (0, 1, 2)'로 
2 이하를 모두 체크할 수 있습니다. 

 

def is_prime2(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

 

또 소수 찾기에 관련된 알고리듬 중 흔히 사용되는 것으론
에라토스테네스의 체(the sieve of Eratosthenes)가 있습니다.
'특정 숫자까지의 모든 소수를 찾아야 하는 경우'에는
이 방법이 아주 효율적입니다. 

 

이 분이 에라토스테네스

출처: https://ko.wikipedia.org

100까지의 숫자 중에 소수를 모두 찾는다고 할 때,
남아 있는 2를 소수로 체크하고, 2의 배수를 모두 지웁니다. 
남아 있는 3을 소수로 체크하고, 3의 배수를 모두 지웁니다. 
4는 2의 배수라 이미 지워져 있습니다. 
남아 있는 5를 소수로 체크하고, 5의 배수를 모두 지웁니다. 
6은 2의 배수라 이미 지워져 있습니다. 
남아 있는 7을 소수로 체크하고, 7의 배수를 모두 지웁니다. 
.....

 

체로 거르는 것과 같죠?

 

코딩하면 다음과 같습니다.

sieve는 체라는 뜻입니다. 

def is_prime3(n):
    sieve = [False, False] + [True] * (n - 1)
    for i in range(2, n + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = False
    return sieve[n]

def find_all_primes(n):
    sieve = [False, False] + [True] * (n - 1)
    primes = []
    for i in range(2, n + 1):
        if sieve[i]:
            primes.append(i)
            for j in range(i * 2, n + 1, i):
                sieve[j] = False
    return primes

 

시간을 측정해 보았습니다. (9999991은 소수입니다.)

속도측정은 데코레이터를 이용했습니다. 
https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8D%B0%EC%BB%A4%EB%A0%88%EC%9D%B4%ED%84%B0-%EC%8B%9C%EA%B0%84-%EC%B8%A1%EC%A0%95

is_prime1(9999991)
is_prime2(9999991)
is_prime3(9999991)
find_all_primes(9999991)

Working Time [is_prime1]: 1.5271806716918945312
Working Time [is_prime2]: 0.0
Working Time [is_prime3]: 3.6415238380432128906
Working Time [find_all_primes]: 3.5460410118103027344

다들 예상하셨겠지만, 위 방법 중 
하나의 소수를 찾을 때는 제곱근까지만 소수를 찾는 함수(is_prime2)가 가장 빠릅니다. 
2부터 모든 소수를 다 찾는 경우에는 에라토스테네스의 체(find_all_primes)가 효율적입니다.