소수(prime number) 판별할때 제곱근 까지만 확인하는 이유

에네토스테네스의 체에서 소수를 구할때도 소수를 판별할때도 제곱근까지만 확인하면, 그 이후의 숫자는 확인을 하지 않아도 된다. 그 이유는?

 

어떤 수 x는 √x 를 기준으로 작은 자연수와 큰 자연수의 곱으로 나타낼 수 있다. √x 보다 작은수 중에 (엄밀하게 같거나 작은수) 약수가 없다면 √x 보다 큰 수에도 약수는 없다. 따라서 √x 까지만 확인하면 되는 것이다.

 

합성수는 소수의 곱이므로 

"  √x  보다 작은 소수가 약수인지만 체크하면 된다"

 

예) 101 이 소수인지 판별하라?

11의 제곱은 이미 101보다 크므로 10 이하의 소수가 101의 약수인지 체크하면 된다.

2, 3, 5, 7 -> 모두 101의 약수가 아니므로 101은 소수이다.