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

소수는 1과 자기 자신만을 약수로 가지는 수입니다. 코딩 테스트에서 자주 등장하는 개념이라, 소수를 판별하는 알고리즘은 꼭 알고 계시는 것이 좋습니다. 이번 글에서는 Python으로 소수를 판별하는 방법 중 대표적인 두 가지를 소개드리도록 하겠습니다.

 

1. 기본 소수 판별법 (완전탐색 방식)

가장 단순하게 먼저 떠올릴 수 있는 방법은 2부터 n-1까지 전부 나누어보는 것입니다. 만약 하나라도 나누어떨어지면 소수가 아니고, 그렇지 않으면 소수로 판단하는거죠.

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
    
print(is_prime(7))   # 출력: True (소수)
print(is_prime(10))  # 출력: False (소수 아님)

⚠️ 단점

이 방법은 아주 단순하지만, 검사 횟수가 많아 수가 커질수록 비효율적입니다.

예를 들어 10000이 소수인지 판단하려면 2부터 9999까지 모두 나누어봐야 하므로 시간이 오래 걸립니다.

그래서 사용할 수 있는 방법이 아래 방법입니다.

 

2. 제곱근까지만 검사하는 방식

실제로는 n의 약수는 항상 $ \sqrt{n} $ 이하 중에 하나는 존재하기 때문에, 2부터 $ \sqrt{n} $ 까지만 나누어보면 됩니다. 이 방법을 적용하면 훨씬 더 빠르게 소수를 판별할 수 있습니다.

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
    
print(is_prime(7))   # 출력: True
print(is_prime(10))  # 출력: False

 

🧠원리

어떤 수 n이 소수가 아니라면, n = a × b 꼴로 약수를 가질겁니다.
여기서 a와 b가 모두 $ \sqrt{n} $ 보다 크다고 가정해보면,

a × b > $ \sqrt{n} \times \sqrt{n} = n $이 되어버리므로 모순입니다.

즉, n이 약수를 가진다면 그 약수 중 하나는 반드시 $ \sqrt{n} $ 이하에 존재하게 됩니다.
그러니까 2부터 $ \sqrt{n} $ 까지만 검사해도 약수가 있는지 없는지를 완전히 판단할 수 있는거죠.

 

예를 들어, 36의 약수는 다음과 같이 짝을 이루게 됩니다.

1×36, 2×18, 3×12, 4×9, 6×6

이렇게 보면, 약수 쌍 중에서 작은 쪽 숫자들은 전부 $ \sqrt{36} = 6 $ 이하입니다.
따라서 그 이하까지만 검사하면 모든 경우를 체크한 것과 같게되는거죠.