[종만북] 소수 판별 O(N ^ 0.5 ) / 정수론 / Python 파이썬

[종만북] 소수 판별 O(N ^ 0.5 ) / 정수론 / Python 파이썬

 

[종만북] 소수 판별 O(N ^ 0.5 ) / 정수론 / Python 파이썬

 

주어진 수 N이 소수인지 판단하는 가장 단순한 방법은, 2부터 N-1 까지 모든 수를 순회하면서 이 중 N의 약수가 있는지 확인하는 것이다.

 

N 이 합성수라면 N = p x q 이고, p <= N ^ 0.5 && q >= N ^ 0.5 이다.

그러므로 N-1 까지 순회하지 않고 N ^ 0.5 까지 순회하도록 최적화 할 수 있다.

 

그리고 2 보다 큰 모든 짝수는 2 를 약수로 가지고 있으므로, 짝수 중 2 와 홀수들만 소수가 될 수 있다.

 

# O(N ** 0.5) 시간에 동작하는 소수 판별 알고리즘

def isPrime(N):
    if (N <= 1):
        return False
    if (N <= 2):
        return True

    # 2의 배수 (짝수) 제외
    if not (N % 2):
        return False

    # 합성수 N = p * q 일 때, p <= (N ** 0.5) && q >= (N ** 0.5) 이므로,
    # ( N ** 0.5 ) 까지 순회하는 것으로 합성수 판별이 가능하다.
    sqrtn = int(N ** 0.5)

    # 3이상의 홀수로 나누어 판별, 짝수를 제외한 경우에 대해서 판별
    for div in range(3, sqrtn+1, 2):
        if not (N % div):
            return False
    return True


print(isPrime(14))