[알고리즘] 에라토스테네스의 체에서 소수 판정 시 제곱근 까지만 확인하면 되는 이유

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

n이하의 모든 소수를 구하려고할 때 효율적으로 구하기 위해 n의 제곱근까지만 확인한다.

 

아래 예시를 보자.

1. n이하의 모든 소수를 구하고자할 때 n은 x와 y에 대해 n = x*y이다. (x와 y는 자연수이다.)

2. n = m*m이다. (m이 n의 제곱근이다.)

3. n = x*y이고 n = m*m이므로 x*y = m*m이다.

 

이 상태에서 x와 y가 자연수인 경우는 아래 3가지 경우이다.

1. x = y = m일 경우

2. x < m, y > m일 경우

3. x > m, y < m일 경우

 

결론

1. x와 y가 자연수가 되려면 위 세가지 경우 중 하나의 경우여야 한다.

2. x와 y의 최소값은 m보다 작거나 같아야한다. (min(x,y) <= m)

3. n의 모든 약수에 해당하는 자연수 x와 y는 x=y=m을 제외하고는 x와 y중 하나는 무조건 m보다 작아야 한다.

4. 결과적으로 m까지만 조사한다면 n이 소수인지 확인할 수 있다.

 

 

추가적으로 n보다 작은 모든 수에 대해 n의 제곱근으로 소수 판정 또한 가능하다.

1. n보다 작은 수 중에 가장 큰 수인 n-1에 대하여 n의 제곱근이 n-1의 제곱근보다 무조건 크다.

2. 위와 같이 n보다 작은 모든 수의 제곱근은 n의 제곱근보다 작으므로 n뿐만아니라 n보다 작은 모든 값에 대해 소수 판정이 가능하다.