소수 판별하기

소수란?

1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수

 

시간복잡도 O(N)인 소수 판별법 

1보다 큰 자연수가 아닌 경우 걸러준다.

2부터 해당 수 - 1 까지 돌면서, 나누어 떨어지면 소수가 아니므로 걸러준다.

이 때 시간복잡도는 해당 숫자 - 1 까지 확인하므로 O(n)이다.

def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False

    return True

 

시간복잡도 O(√N) 인 소수 판별법

숫자가 15 이라면 1, 3, 5, 15 이 약수인데 이때 루트 15 (3,xx) 까지만 확인해도 된다.

숫자가 4이라면 1, 2, 4 이 약수인데 루트 4 (2) 까지만 확인해도 된다.

즉 숫자에 루트를 씌운 값이 중간값이므로 그 값까지 확인해서 나누어떨어지면 소수가 아니다.

2에서 n-1 까지 도는 것이 아니라 2에서 n의 제곱근 까지 돈다. 

이 때 시간복잡도는 해당 숫자의 제곱근까지 확인하므로 O(√N) 이다.

import math

def is_prime(number):
    if number in (0, 1):
        return False
    
    for i in range(2, int(math.sqrt(number))+1): # n의 제곱근(정수화)
        if number % i == 0:
            return False

    return True