에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유

  흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다.

 

 

  n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다.

-> 예를들어 12는 2*6 혹은 3*4 등으로 나타낼 수 있다. a, b가 자연수라는 부분이 중요하다.

 

  또 m = sqrt(n) 이라고 하면 n = m * m 이라고 할 수 있다.

-> 여기서 sqrt는 square root 즉 제곱근을 의미한다. 수식으로 나타내면 다들 알 것이다.

 

  n = a*b이고, n = m*m 이라 했으므로 a*b = m*m 이다. (a,b는 자연수이고 m은 n의 제곱근)

 -> 그럼 이 상태에서 a랑 b가 자연수가 되려면 다음의 세가지 경우 중 하나만 가능하다.

A. a=m 이고 b=m (n이 4와 같은 경우라서 m도 2처럼 자연수라면 가능하다.)

B. a<m 이고 b>m

C. a>m 이고 b<m

 

  a, b가 자연수가 되려면 항상 위의 세가지 중 하나가 되고, 그렇다면 min(a, b) <= m 인것을 알 수 있다. (a와 b 중 작은 것은 m보다 작거나 같다.)

 

  즉, n의 모든 약수에 해당하는 a와 b가 어떠한 약수이더라도 둘 중 하나는 무조건 m(=sqrt(n)) 이하 이므로, m까지만 조사한다면 n이 소수인지 알 수 있게 되는 것이다.

 

  그럼 이건 정확히 n에만 국한된 것이지, n 이하의 모든 수에 대해 만족하진 않는다고 생각할 수 있다. 하지만 n보다 작은 것 중 가장 큰 수인 n-1만 해도 sqrt(n)>sqrt(n-1) 이다. 즉 n보다 작은 수는 모두 sqrt(n) 내에 포함되므로 n 뿐만 아니라 n 미만의 모든 값에 대해 소수 판정이 가능하다.