소수 판정법

💡

<문제 해결을 위한 알고리즘 with 수학> 책을 참고 했습니다.

---

소수 - 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

단순한 소수 판정법

---

어떤 수가 소수인지 판정하려면 어떤 방법을 사용해야 할까?

먼저 가장 단순한 방법을 생각해보자.

소수는 1과 자기 자신만을 약수로 가지므로 1과 자기 자신을 제외한 수들로 나눴을 때 나누어지지 않으면 소수라는 것을 알 수 있다.

예) 53 → 2~52까지의 자연수로 나누어본다.

시간복잡도 - $O(N)$

빠른 소수 판정법

---

사실 2부터 $N-1$까지 전부 확인할 필요는 없고, $\sqrt{n}$ 까지만 나누어보면 소수인지 판정할 수 잇다.

예) $\sqrt{53} = 7.28...$ 이므로 2, 3, 4, 5, 6, 7까지만으로 나누어보면 “53은 소수이다”라고 말할 수 있다.

시간복잡도 - $O(\sqrt{N})$

이 판정법이 유효하다는 것을 귀류법으로 증명할 수 있다.

증명할 명제는 다음과 같다.

“1과 $N$을 제외한 $N$의 약수가 존재할 때, 그 중에서 최솟값을 a라고 하자. 이때 $a ≤ \sqrt{N}$ 이다.

이것이 성립하지 않는다고 가정해보자. 즉 $a > \sqrt{N}$이라고 가정해보는 것이다.

$a$는 $N$의 약수이므로, 약수의 성질로 인해서 $ab = N$이 되는 양의 정수 $b$가 존재한다.

그리고 1과 $N$을 제외한 약수 중에서 최솟값이 $a$이므로 b는 a보다 크거나 같아야 한다.

그런데 $a > \sqrt{N}$ 이므로 $b < \sqrt{N}$ 가 되고, 이는 최소 약수가 a라는 것과 모순 되기 때문에

$a ≤ \sqrt{N}$ 이다.

구체적인 예로 “1이 아닌 77의 약수 중에서 가장 작은 것”이 11이라고 가정해보자.

그런데 11 x 7 = 77이 되므로, 77의 약수에 7이 포함된다. 따라서 11이 최소의 약수라는 것과 모순된다. 최소인 약수가 $\sqrt{7}$을 넘는 경우, 이러한 일이 반드시 일어난다.

응용 예 : 약수 모두 출력하기

---

다음의 과정으로 N의 약수를 모두 출력할 수 있다.

1. i = 1, 2, 3, … $\sqrt{N}$일 때, N이 i로 나누어지는지 확인한다.

2. 나누어지는 경우 i와 N/i는 약수이다.

시간복잡도 - $O(\sqrt{N})$

예) N = 100이라면 1부터 10까지 나누어 봤을 때, 나누어진다면 나눈 수와 몫이 약수가 된다.

이렇게 100의 약수인 1, 2, 4, 5, 10, 20, 25, 50, 100을 구할 수 있다.

왜 $\sqrt{N}$ 까지만 나눠보면 되는 걸까?

100을 “100의 약수 중 11 이상인 것($\sqrt{N}$ 보다 큰 자연수)”으로 나눈 몫은 “100의 약수 중 10 이하인 것”이 된다.

왜냐하면 N = $\sqrt{N} \times \sqrt{N}$ 이기 때문에 한쪽을 $\sqrt{N}$ 보다 큰 수로 나눈다면 당연히 다른 한쪽은 $\sqrt{N}$ 보다 작아질 수 밖에 없기 때문이다.

그렇다면 N의 약수를 찾아내기 위해서 N을 굳이 $\sqrt{N}$ 보다 큰 수로 나눠볼 필요가 없다.

왜냐하면 100을 25로 나누면 4가 되는데, 이 25라는 약수는 4로 나누는 시점에 찾을 수 있기 때문이다.

참고자료

---

https://blog.encrypted.gg/?page=289

<문제 해결을 위한 알고리즘 with 수학> - 위키북스

Uploaded by N2T