거북이처럼 천천히

이미 알고 있는 소수 판별법 이미 알고 있는 소수 판별법은 다음 두 가지 방법이었다. 문제 : 자연수 X이 소수인가? 반복문을 이용하여 자연수 X을 2 ~ X-1까지 나눠봐서 한 번이라도 나머지가 0인 경우가 나오면 자연수 X은 소수가 아니다. 약수는 쌍을 이룬다는 점을 이용하여 2 ~ X-1까지가 아닌 2 ~ X/2까지 나눠봐서 자연수 X이 소수인지 판별할 수 있다. 하지만, 2 ~ root(X)이하까지만 나눠봐도 해당 숫자가 소수인지를 효율적으로 판별할 수 있다고 한다. 직감적으로 "왜 root(X) 이하까지만 나눠도 되는가?"를 이해할 수 없어 수식적으로 증명해 보자 한다. 왜 root(X) 이하까지만 나눠도 되는가? 가정 : 자연수 X은 소수가 아닌 합성수이며, 자연수 X은 M * N으로 표현할 ..