소수(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