소수 판정 (Primality Test)
다음과 같은 문제가 있다.
이 문제를 어떻게 풀어야 할까? 가장 나이브하게 생각해보자. 그것은 바로 $2$부터 $n$-$1$까지의 수를 나눠보는 것이다. 시간 복잡도는 $O(n)$이 되겠다.
그럼, 수의 범위를 한 번 키워보자.
이 문제도 $n$-$1$까지 나눠본다면 풀리긴 할 것 같다. 운이 좋아서 $n$이 $2$의 배수, 혹은 $3$의 배수라면 눈 깜빡이는 속도보다 빠르게 결과가 나올 것이다.
최악의 경우?
위 문제에서 가장 많은 연산을 하는 경우는 어떤 경우일까? 간단하다. $n$을 $10^{12}$보다 작은 가장 큰 소수로 두면 된다.
이 경우 사실상 $n$에 근사한 연산 횟수를 갖게 될 테고, 결과를 도출하는 데에 적지 않은 시간이 필요할 것이다.
결국 우리는, 새로운 방식을 고찰해야한다.
절반까지만 나눠본다면?
가장 우선적으로 생각해볼 수 있는 최적화 방식이다.
연산량이 평균적으로 절반씩 감소하겠지만, 앞서 이야기한 범위 및 최악의 경우를 생각해보자. 결국 $O(\frac{n}{2})$ = $O(n)$이고 여전히 연산량은 많다.
수론적 접근과 결론
결론부터 말하자면, $\sqrt{n}$까지만 나눠봐도 된다. 왤까 ?
$1$보다 큰 양의 정수 $n$이 소수가 아닌 합성수라고 해보자. 그럼 $n$은 어떤 두 양의 정수의 곱으로써 표현할 수 있다. 이를 $n = p \times q$ $(1 < p, q < n)$ 라 하자.위 식에서 $\sqrt{n}$을 기점으로 생각해보면, 다음 세가지 경우로 나눌 수 있다.
이를 관찰했을 때, 적어도 하나의 인수는 $\sqrt{n}$보다 작거나 같음을 알 수 있다.
구체적으로 합성수 $n$에 대해 $n = p \times q$ $(1 < p, q < n)$는 $min(p, q) ≤ \sqrt{n}$를 만족한다는 것을 알 수 있다.
따라서, $n$에 대해 $2 ≤ p ≤ \sqrt{n}$ 인 $p$들을 조사해보면 $q = \frac{ n }{p}$로 구할 수 있으므로 소수 판정을 $O(\sqrt{n})$에 해낼 수 있게 된다.