소수 판별

소수를 판별하는 알고리즘을 짜라고 한다면 누구나 반복문을 사용하여 모든 수를 나눠보는 것을 생각할 것이다.

나도 그걸 제일 먼저 생각해냈으나 너무나 당연하게도 시간복잡도 측면에서 아웃이다..

하지만 완전히 틀린 이야기는 아니다.

먼저 소수 판별하는 방법을 생각해보자.

---

소수 판별 알고리즘

반복문을 사용하여 하나하나 나눠봐야하는 것을 사실이다. 하지만 굳이 1 부터 n까지 모두 나눠볼 필요는 없다.

힌트는 제곱근이다.

16라는 숫자의 약수를 생각해보자.

[1, 2, 4, 8, 16]

4를 기준으로 양 옆을 곱한 수가 해당 숫자가 되는 것을 알 수 있다.

(2 X 8) 과 (8 X 2) 이런식으로 대칭이 된다는 것이다

여기서 4라는 숫자는 16의 제곱근이다.

즉, 제곱근 이상의 숫자는 굳이 또 나눠볼 필요가 없다는 것이다!

코드로 짜보면 다음과 같이 나타낼 수 있다.

import math

def checkPrime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

print(checkPrime(10)) # False
print(checkPrime(7)) # True

해당 코드의 시간복잡도는 O(N^(1/2))가 된다.

만약 하나하나 모든 수를 나눠보는 코드를 짰다면 그 코드의 시간복잡도는 O(N)이 되었을 것이다.