주요 내용
Trial division
문제의 정의
간단한 예/아니요 문제에 대답할 수 있는 기계를 만들어야 합니다. 주어진 정수 n은 소수일까요?
이 기계가 제대로 작동하게 하기 위해 기계 내부에서 어떤 일이 일어나야 하는지 생각해 봅시다. 기계는 알고리즘이라고 하는 어떤 명령에 기초하여 여러 단계를 순서대로 따르는 일만 할 수 있습니다. 준비 운동으로 여러분 머리 속에 어떤 알고리즘이 있는지 알아봅시다. 다음 질문의 해답은 무엇일까요: 49는 소수인가요?
…
아니라고요? 어떻게 알았나요? 아마도 1보다 크고 49보다 작은 49의 약수를 찾았을 것입니다. 구구단을 기억하지 못한다면 다음과 같은 순서에 따라 계산했을 것입니다.
- 2로 49를 나눌 수 있습니까? 아니요
- 3으로 49를 나눌 수 있습니까? 아니요
- 4로 49를 나눌 수 있습니까? 아니요
- 5로 49를 나눌 수 있습니까? 아니요
- 6으로 49를 나눌 수 있습니까? 아니요
- 7로 49를 나눌 수 있습니까? 예
49의 인수(7) 를 찾았으므로 49는 합성수입니다.
벽 세우기
그런데 2971215073 가 소수인지 묻는다면 어떻게 할까요?
아직도 확인하고 있나요? 수천 번 시험해보아도 약수를 발견하지 못할겁니다. 질문의 핵심은 언제 검사를 그만둔 후 그 수가 소수라고 말할 수 있을까?라는 것입니다.(이를 벽이라고 부르기로 합시다) 출발점으로 우리는 벽이 반드시 n-1이어야 한다는 것(n으로 n을 나눌 수 있기 때문에)을 알고 있습니다. 2971215072 까지 검사하다 보면 약수를 발견하거나 ( n 이 합성수라는 것을 증명합니다) 약수를 발견하지 못합니다 (n 이 소수라는 것을 증명합니다).
개선된 벽 세우기
앞의 과정대로 답을 찾을 수는 있겠지만 벽을 움직여서 시간을 절약할 수 있을까요? 우리가 실제로는 첫번째, 또는 가장 작은 약수를 찾고 있다는 것을 잊어선 안됩니다. 종종 가장 작은 인수는 2가 될 수도 있고 더 큰 수일 수도 있습니다. 그러면 '가장 작은 약수의 크기는 얼마나 되어야 하나?'라고 궁금해질 것입니다.
모든 합성수 n은 2개 이상의 소수로 이루어진다는 것을 기억하세요. n= P * P …
n이 똑같은 수인 두 인수로 이루어진 경우 P가 최댓값이 됩니다. 이를 제곱수라고 하는데 9 (9 = 33)나 49 (49 = 77)와 같은 수입니다. 이에 기초한 최악의 경우의 시나리오를 고려하려면 그냥 n의 제곱근에서 벽을 세우면 됩니다!
기억하세요: n의 제곱근까지 검사해도 약수가 발견되지 않았다면 n은 분명히 소수입니다. 직접 증명해 보세요. (이 글 마지막에서 증명을 볼 수 있습니다.)
Trial division 알고리즘
끝입니다. 이제 다음 단계로 나아갈 준비가 되었습니다. 우선 trial division 알고리즘을 글로 풀어 써 봅시다.
- 입력값 정수 n을 받아들입니다.
- {2... sqrt(n)} 까지의 각 정수 x에 대하여 n이 x로 나누어떨어지는지 검사합니다.
- 나눠지는 약수가 있다면 n은 합성수이고 아니면 n은 소수입니다.
프로그래밍 경험이 있다면 CS스크래치 패드 를 열어서 이 함수를 작성해 보세요. 프로그래밍 경험이 없는 분들은 제공된 완성된 버전을 활용하여 함수를 작성해 보세요. (참고로 프로그래밍을 하지 않고도 이 수업을 배워볼 수 있습니다.)