7. 소수판정법
문제해결을 위한 알고리즘 입문
이번에는 자연수 N이 소수인지 아닌지를 판단하는 문제를 다루어 봅니다. 또한, 역리법이라는 전형적인 증명기법을 소개하고 알고리즘의 정당성을 증명하는 방법을 배워봅시다.
(1) 간단한 소수판정법
우선 53이 소수인지 판단해 봅시다. 아래와 같이 2부터 52로 나눌 수 있는지 확인하는 방법도 생각할 수 있지만, 계산하는데 시간이 오래 걸립니다.
일반 정수 N에 대해서도 마찬가지로 2에서 N-1로 나눌 수 있는지 여부를 조사하여 소인수 판정을 할 수 있습니다. 예를 들어, 아래 코드와 같은 구현을 생각할 수 있습니다. 하지만 계산량은 O(N)으로 느리고, 예를 들어 이 방법으로
가 소수인지 아닌지를 계산하면 PC에서도 10분이상 소요됩니다.
(2) 빠른 소수판정법
사실 2부터 N-1까지 모두 조사할 필요가 없고,
까지 조사하여 나눌 수 없으면 소수라고 해도 무방합니다. 반대로 모든 합성수는
의 정수 중 하나로 나눌 수 있습니다. 예를 들어,
까지 나뉘지 않으면 "53은 소수"라고 말할 수 있습니다. 반면에 77의 경우,
를 살펴보지만, 7로 나뉘어져 있어 제대로 합성수라고 판단합니다.
아 알고리즘 계산량은
이며, 아래 코드와 같은 구현을 생각할 수 있습니다. 이것은 이전 방법보다 훨씬 빠르며, 예를 들어,
가 소수인지 아닌지 확인하는데 필요한 계산시간은 0.01초정도에 불과합니다. 그런데 왜 이 알고리즘이 모든 경우에 제대로 작동하는 것일까요? 그 이유를 설명하기 위한 증명기법은 나중에 설명합니다.
⑶ 배리법(Proof by Contradiction)
다음과 같은 흐름으로 '사실 F가 옳다는 것'을 증명하는 기법을 배리법이라고 합니다.
사실 F가 틀렸다고 가정하면 모순이 발생한다는 것을 유도합니다.
예를 들어, '삼각형의 내각 중 적어도 하나는 60도 이상이다'라는 사실은 다음과 같은 절차로 증명할 수 있습니다.
사실이 정확하지 않다고 가정하면 바로 모든 내각이 60도보다 작다고 가정합니다.
이 경우 삼각형의 내각의 합은 (60도 미만) + (60도 미만) + (60도 미만) + (60도 미만) = (180도 미만)이 됩니다.
그러나 삼각형 내각의 합은 반드시 180도이어야 합니다.
따라서, '사실이 정확하지 않다'는 가정은 모순이 발생합니다.
⑷ 알고리즘의 정당성 증명
다음은 (2)에서 설명한 소수 판단 알고리즘이 옮다는 것, 즉 N이 합성수라면 2이상 N이하의 약수가 존재한다는 것(사실 F라고 하면)은 역리법을 이용하여 아래와 같이 증명할 수 있습니다.
사실 F가 성립하지 않는다고 가정합니다. 즉, N이 합성수이고 1이 아닌 최소 N의 약수 A가 N을 초과한다고 가정합니다.
약수의 성질상 A X B = N이 되는 양의 정수 B가 존재합니다. 이때 B는 N의 약수입니다.
그러나,
이상의 최소 약수가 A라는 것과 모순됩니다.
따라서 가정은 성립하지 않으며 사실 F가 맞습니다.
구체적인 예로 '1이 아닌 최소 77의 약수'가 11이고, 사실 F가 성립하지 않는다고 생각해 봅시다. 그런데, 11 X 7 = 77이 되므로, 77 약수에 7이 포함되어 11이 최소 약수라는 사실과 모순됩니다. 최소 약수가
을 초과하는 경우, 이런 일이 반드시 발생하게 됩니다.
참고로 25, 49, 121과 같은 '소수의 제곱으로 표현되는 수'는 2이상에서 최소 약수가 정확히 N이 된다는 점에 주의해야 합니다.
⑸ 응용하기: 약 몇가지 열거하기
마지막으로 소수판정법과 비슷한 다음절차로 N의 약수를 열거할 수 있습니다.
예를 들어, N=100인 경우, 1부터 10까지 시험삼아 나누어보고, 나뉜 것에 대해서는 그 수와 "100 ÷ 그 수"를 더하면 100의 약수가 모두 열거됩니다.
이것이 잘되는 이유는 100을 '11이상 100의 약수'로 나누면 '10이하 100의 약수'가 되기 때문입니다.
예를 들어, 100을 25로 나누면 4가 되는데, 25라는 약수는 4로 나눴을 때 이미 발견할 수 있습니다.
이 알고리즘의 계산량은
입니다. 아래 코드는 N의 약수를 모두 출력하는 프로그램입니다. (작은 순서대로 출력하는 것은 아닙니다)
⑹ 연습문제
문제7-1.
(2)에서 설명한 방법을 사용하여 자신의 나이가 소수인지 아닌지를 판단해보세요.
문제7-2.
자연수 N을 소인수분해하는 프로그램을 작성하세요.
소인수분해란?
286 = 2 X 11 X 13
20211225 = 3 X 5 X 5 X 31 X 8693
와 같이 자연수를 소수의 곱셈형태로 표현하는 것을 말합니다. 계산량은
인 것이 바람직합니다.
© 2024 ZeR0, Hand-crafted & made with Damon JW Kim.
Profile: https://gaebal.site
강의 및 개발, 컨설팅 문의: https://talk.naver.com/ct/w5umt5
