소수 판정과 에라토스테네스의 체

소수(Prime number)의 정의

1과 자기 자신 으로만 나누어 떨어지는 자연수

소수 판정법

주어진 $n$이 소수인지 판정

1. $ 1 < k < n $ 인 $ \forall k \in \mathbb{N} $ 에 대하여 $n \ \text{mod} \ k = 0$ 인지 검사하는 방법이 있다.

최악의 경우 $O(n)$의 시간복잡도를 가진다.

2. 검사 대상을 $ 1 < k \le \sqrt{n} $ 인 $ \forall k \in \mathbb{N} $로 축소해볼 수 있다.

$ \sqrt{n} $ 이하의 자연수만 검사해도 되는 이유는

$ \sqrt{n} \leq k \leq n$ 인 임의의 $ k \in \mathbb{N} $가 $n$의 약수일 때, $n/k$ 또한 $n$의 약수이다

$ \sqrt{n} \leq k \leq n$ 이면 $ n/k \leq \sqrt{n} $이기 때문에 $ \sqrt{n} $ 이하의 자연수만 검사해도 충분하다.

최악의 경우 시간 복잡도는 $ O(\sqrt{n}) $ 이다.

3. 위 방법을 조금 더 최적화 해보면, $2$를 제외한 모든 짝수는 소수가 아니기 때문에

$2$, 그리고 $ 2 < k \le \sqrt{n} $ 인 홀수에 대해서만 나누어 떨어지는지 검사하는 방법을 사용해볼 수 있다.

def is_prime(k):
    if not k&1 or k<2: return False
    for i in range(3, int(k**.5)+1, 2):
        if not k%i: return False
    return True

밀러-라빈(Miller-Rabin) 소수 판별법

큰 수에 대해 좀 빠르게 소수 판별을 해야 한다면 밀러-라빈 소수 판별법 사용을 고려해볼 수 있다.
밀러-라빈 소수 판별법은 확률적 알고리즘으로, 잘못된 판정 결과가 나올 수 있다.
(해당 주제는 추후 따로 정리할 예정)

에라토스테네스의 체

특정 범위 내에 존재하는 모든 소수를 판정해아 한다면 에라토스테네스의 체를 사용해볼 수 있다.
에라토스테네스의 체의 작동 원리는 다음과 같다.


1. 범위 내의 $1$보다 큰 수 중 가장 작은 수를 선택
2. 1.에서 선택한 수의 배수를 전부 삭제 (자기 자신은 제외).
3. 선택되지 않은 남은 수 중 가장 작은 수를 선택하여 2.~3.의 과정 반복

a = [0]*2 + [1]*(n-1)
primes = []

for i in range(2, int(n**.5)+1):
    if a[i]:
        primes.append(i)
        for j in range(i*2, n+1, i):
            a[j] = 0