[python]소수 판별 알고리즘

들어가며

이글은 동빈나님의 이코테 강의를 보며 정리한 글입니다.

소수 판별 알고리즘

1과 자기자신을 제외한 약수를 갖고있지 않는 수를 우리는 소수라고 합니다. 예들 들어 아래와 같이 6, 7을 분류할 수 있습니다.

• 6 : 1, 2, 3, 6을 약수로 갖고 있으므로 소수가 아닙니다.
• 7 : 1과 7만을 약수로 갖고 있으므로 소수입니다.

알고리즘 문제를 풀 경우 이러한 소수를 찾는 알고리즘 문제를 만났을 때, 효율적으로 소수를 판별하는 알고리즘에 대해서 알아봅시다.

1. 일반적인 소수 판별

소수의 특징을 이용해서 가장 간단하게 소수 판별 알고리즘을 구현할 수 있습니다. 특정 자연수 $N$을 2부터 $N-1$까지 모두 반복적으로 나뉘어 떨어지는지 확인한 후, 소수인지 아닌지 판별하면 됩니다.

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

이렇게 구현한 소수 판별 알고리즘은 최대 $N$만큼의 연산이 필요하므로 $O(N)$의 시간복잡도를 갖습니다.

2. 약수의 성질을 이용한 소수 판별

사실, 어떠한 자연수 $N$의 약수는 모두 곱셈 연산에 대해 대칭적인 구조를 갖습니다. 예를 들어, 아래와 같은 특징이 있습니다.

• $1\times16=16$
• $2\times8 = 16$
• $4\times4 = 16$
• $8\times2 = 16$
• $16\times1=16$

이처럼 모든 곱셈은 대칭적인 구조입니다. 따라서, 모든 수를 확인하지 않고, $N$의 제곱근까지만 확인하면 똑같이 소수판별을 진행할 수 있습니다.

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

이렇게 되면 자연수 $N$에 대하여 연산은 최대 $\sqrt{N}$만큼만 진행합니다. 따라서, 시간복잡도는 $O(\sqrt{N})$를 갖습니다.

에라토스테네스의 체

만약 특정 자연수 $N$이 아니라 특정 범위에 해당하는 모든 약수를 구해야 한다면 어떨까요? 위 알고리즘들을 이용해서 연산을 수행해도 되겠지만, 그렇게 되면 아무리 좋게 알고리즘을 구현하더라도 복잡한 시간복잡도를 갖게 될 것입니다. 하지만 에라토스테네스의 체 알고리즘을 이용하여 대량의 소수를 한꺼번에 판별할 수 있습니다.

에라토스테네스의 체 알고리즘은 모든 자연수를 배열로 나열합니다. 예를 들어 1부터 25까지의 수 중 소수만 출력해야 된다고 하겠습니다. 그렇다면 배열은 아래와 같습니다.

이제, 2부터 2를 제외한 2의 배수를 모두 지워줍니다.

마찬가지로 2다음 3부터 똑같이 3을 제외한 자신의 배수를 모두 지웁니다.

이제 4를 진행해야 하는데, 4는 이미 2에서 지워진 수입니다. 따라서 건너 뜁니다. 이 행위를 반복합니다.

이제 모든 소수가 판별되었습니다. 이렇게 결과적으로 1, 2, 3, 5, 7, 11, 13, 17, 19, 23이 결과로 출력됩니다.

이를 코드로 표현하면 아래와 같습니다.

def prime_number_sieve(n):
    nums = [i for i in range(n+1)]
    ret = []
    for i in range(2, n+1):
        if nums[i] == 0: continue
        ret.append(nums[i])
        for j in range(i+i, n+1, i):
            nums[j] = 0
    return ret

이렇게 에라토스테네스의 체로 여러 소수를 한번에 판별하는 방법에 대해서 알아보았습니다. 이 방법은 $O(N\log{(\log{N})})$의 시간복잡도를 갖습니다.