N까지의 소수 검사할때 N의 제곱근(square root of N) 까지만 하는 이유

N까지의 소수 검사 관련 코드를 조금 더 빠르게 하는 여러가지 방법이 있습니다.

그중 이해하기 쉬운 테크닉(?) 중 하나가 N까지 검사하지 않고 N의 제곱근( square root of N) 까지만 검사하는 것인데요, 코드로 설명하면 다음과 같습니다.

def isPrime(n):
    if n == 1: return False
    if n == 2 or n == 3: return True
    if n%2 == 0: return False
    for i in xrange(3, int(n**0.5)+1, 2):
        if n%i == 0:
            return False
    return True

이것이 성립하는 이유가 좀 궁금해져서 알아보고 생각해봤습니다.

어떤 수 n이 1과 자신이 아닌 두 수의 곱으로 되어 있다고 생각해봅시다. (즉, 소수가 아님)

n = a*b 이고 n' 은 n 의 제곱근이라고 표현합시다.

여기서 만약,

a >= n' 이면, a*b = n = n'*n' 이므로 b<=n' 가 됩니다.

따라서 n' 까지만 검사를 하면 합성수를 이루는 a, b 중 작은 수(위에서는 b)까지는 충분히 체크할 수 있고, 합성수가 존재하지 않으면 소수라고 할 수 있습니다.