소수 판정법 알아보기

자연수를 소수인지, 아닌지 판단하는 가장 쉬운 방법은 판단하는 숫자보다 작은 숫자로 계속 나누어 보는 것이다. 예를 들어, 자연수 n이 소수인지 알기 위해 2,3,4, ~ , n-1까지의 수로 나누어 보는 것이다.

 

조금 더 나아가면, $n$이 소수인지 알지 위해 $\sqrt{n}$보다 작은 소수로 나누어보면, 더욱 계산과정을 줄이며 소수인지 아닌지를 판단할 수 있다. 왜냐하면, $n$이 합성수라면, 적어도 $n=ab$, ($1<a,b < n)$으로 표현할 수 있고, 둘 중 적어도 하나는 $\sqrt(n)$보다 작기 때문이다.

 

소수 판정법

즉, $n$이 소수인지 알기 위해 $\sqrt{n}$보다 작은 소수로 나누어 보는 것이다.

 

에라토스테네스 체

이러한 방법과 같은 원리가 '에라토스테네스의 체'를 이용해 소수를 판정하는 것이다.

에라토스테네스 체

에라스토 테네스(Eratosthenes)는 알렉산드리아에서 왕자의 개인 교습 교수, 알렉산드리아의 박물관 관리자로 일했다. 에라토스테네스는 지구의 둘레를 최초로 정확하게 측정했으며, 지도를 만들었다.

 

에라토스테네스 체의 단점은 큰 자리의 숫자는 판단하기 어려운 단점이 있다. 에라토스테네스의 체를 이용한 방법으로 슈퍼컴퓨터를 사용한 최근 연구에서 100자리 숫자를 소수 판단하는데 최소한 $10^{35}$년 정도가 걸린다고 한다. 슈퍼컴퓨터의 계산으로도 매우 힘든 일이라 할 수 있다.

 

현재에는 큰 자연수를 판단하기 위한 방법으로 'APRCL 판정법(또는 페르마 판정법)'이 사용되고 있다. 이 판정법을 이용하면, 100자리의 자연수의 소수 판단은 40초 정도가 걸린다고 한다.

 

APRCL 판정법(페르마 판정법)

$p$가 소수이면, $p$보다 작은 임의의 수 $a$에 대해서 $a$와 $p$가 서로소일 때, $a^{p-1}-1$을 $p$로 나누어 떨어진다.