자연수 N이 소수(prime number)인지 확인하고 싶습니다.

가장 잘 알려진 의사코드(pseudocode) 은 다음과 같습니다. 

isPrime(n) {

for ( from i = 2 to i  = √n )

if ( n % i == 0)

return false;

end for

return true;

}

2부터 √n 까지 하나하나 나눠보고 나머지가 0이 되는 순간이 있다면 소수가 아니라고 판단하고 false를 반환합니다.

반대의 경우 for문을 안전하게 빠져나오게 되고 소수라고 판단되어 true를 반환합니다.

그러면 왜 2부터 까지 모두 나눠보지 않고 √n 까지만 나눠보는 걸까요.

언뜻 생각해보면 알쏭달쏭하지만 조금 더 생각해보면 매우 간단한 아이디어입니다. 

먼저 자연수 n이 합성수라고 가정합니다. 

n이 합성수라면, 즉 소수가 아니라면 1과 n말고 다른 인수들을 가진다는 말이겠죠.

n 을 p와 q의 곱이라고 해보겠습니다. (p와 q는 1과 n이 아닌 자연수)

p와 q 모두 위의 의사코드에서 걸리지 않으려면 둘다 √n 보다 커야 합니다.

p와 q가 √n 보다 크다면 n은 √n 보다 큰 수와 √n 보다 큰 수의 곱이고 여기서 모순이 발생합니다.

따라서 합성수 n = p * q * ㆍㆍㆍ* r * s 에서 n의 인수들 중 적어도 하나는 √n보다 작을 수 밖에 없습니다.

그리고 그 인수는 위의 코드에서 걸리게 되는거죠.