소수 판별 알고리즘

특정한 수의 소수 판별

 특정한 수가 소수(Prime number)인지 여부를 판별하기 위해서는 해당 수에 이르기까지 모든 수를 나누어보고 나머지가 0인지 확인하면 됩니다.

import math

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

is_prime_number(1e100)

단 이 경우엔 x가 매우 큰 값일 경우 계산해야 하는 경우의 수가 많아져 결과적으로 효율성이 저하됩니다. 따라서 이를 개선하기 위해서 약수(Dvisor)의 성질을 알고 있다면 좋습니다. 모든 수는 자신의 모든 약수에 대해서 대칭적인 형태를 보입니다.

 16을 예로 들었을 때, 16의 약수는 1, 2, 4, 8, 16이며 1 x 16 = 2 x 8 = 4 x 4 = 16으로 모두 같습니다. 이러한 성질을 이용하여 'x 미만의 전체 수가 아닌 가운데 약수까지만 확인'해보는 방법론을 취할 수 있습니다. 즉 x의 제곱근까지만 확인하면 모든 수에 대해 소수를 판별한 것과 같습니다.

import math

def is_prime_number(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

is_prime_number(1e100)

 

에라토스테네스의 체

 위에서는 특정한 수가 소수인지를 판별했으나, 구간 내에 모든 소수를 출력하는 경우는 '에라토스테네스의 체' 알고리즘을 사용할 수 있습니다. 절차는 다음과 같습니다.

---

1. 2부터 N까지의 모든 자연수를 나열한다.

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3. 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다).

4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

---

 에라토스테네스의 체 알고리즘은 시간복잡도가 O(NloglogN)이므로, 데이터의 개수가 100만개라고 하더라도 부담없이 사용할 수 있습니다. 따라서 1부터 1000까지의 수에 대해서 소수를 모두 구하려는 경우 다음과 같이 코드를 작성할 수 있습니다.

import math

n = 1000
array = [True for i in range(n + 1)]
array[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1
            
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')