[알고리즘] 소수 판별 알고리즘(파이썬)

소수 판별 알고리즘에 대해서 정리할 필요성을 느껴 정리해본다.

 

소수(Prime Number)란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다.

 

---

가장 기본적인 소수 판별 함수

# 1. 가장 기본적인 소수 판별 함수

def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, x):
    
        # x가 해당 수로 나누어떨어진다면 소수가 아니다.
        if x % i == 0:
            return False
            
    # 나누어지지 않고 반복문이 끝나면 소수이다.
    return True

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

2부터 x -1 사이에서 x의 약수가 존재하는지 파악한다.

약수가 존재할 경우 False를 return한다. -> 소수가 아님.

약수가 존재하지 않을 경우 반복문이 끝난다. -> 소수임.

 

x 까지 모든 수를 파악하므로 시간 복잡도는 O(x)이다.

 

 

---

약수의 성질

약수의 성질

16의 모든 약수를 파악하면, 4를 기준으로 약수는 대칭을 이룬다. 

 

4는 16의 제곱근이므로, 판별할 수의 제곱근까지 비교하고 그때까지 소수가 아닐 경우 해당하는 수는 소수인 것을 알 수 있다.

 

 

 

 

개선된 소수 판별 함수

# 2. 개선된 소수 판별 함수
import math

def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
    
        # x가 해당 수로 나누어떨어진다면 소수가 아니다.
        if x % i == 0:
            return False
            
    # 나누어지지 않고 반복문이 끝나면 소수이다.
    return True

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

 

 

2부터 x의 제곱근까지 반복하므로 시간복잡도는 O(√x)이다.

 

 

 

Reference: 소수 판별 알고리즘