파이썬(Python)에서 소수를 찾는 3가지 방법과 성능 비교

소수란 무엇인가?

소수(素數, Prime Number)는 1과 자기 자신 외에는 어떤 수로도 나누어 떨어지지 않는 양의 정수입니다. 예를 들어 2, 3, 5, 7, 11 등이 대표적인 소수입니다. 주어진 수가 소수인지 판별하는 것은 오랫동안 사랑받아 온 프로그래밍 과제 중 하나이며, 이를 해결하는 방법은 여러 가지가 있고 각 방법마다 효율성도 크게 다릅니다.

이 글에서는 파이썬으로 소수를 찾는 세 가지 대표적인 방법을 살펴보고, 실제 실행 시간을 측정하여 어느 방법이 가장 효율적인지 비교해 보겠습니다.

방법 1: 모든 약수 검사하기

가장 직관적인 방법입니다. 2부터 해당 숫자보다 하나 작은 수까지 모든 정수로 나누어 보고, 나누어 떨어지는 수가 하나도 없다면 그 수를 소수로 판정합니다.

예제 코드

import time

# 소수 판별 함수
def check_prime(final_val):
    if final_val <= 1:
        return False
    for divisor in range(2, final_val):
        if final_val % divisor == 0:
            return False
    return True

# 시작 시간 기록
start_time = time.time()

# 1부터 10000까지 소수 개수 세기
cnt = 0
for n in range(1, 10001):
    cnt += check_prime(n)

print('10000까지의 소수 개수:', cnt)

# 종료 시간 기록
end_time = time.time()
print('소요 시간:', end_time - start_time)

실행 결과

10000까지의 소수 개수: 1229
소요 시간: 약 2.31초

이 방식은 2부터 N-1까지 모든 수를 검사하므로 반복 횟수가 많고, 숫자가 커질수록 실행 시간이 급격히 늘어나는 단점이 있습니다.

방법 2: 제곱근(√N)까지만 검사하기

수학적으로 어떤 수 N이 소수가 아니라면, N은 반드시 √N 이하인 약수를 가진다는 성질이 있습니다. 따라서 √N까지만 검사해도 충분하며, 반복 횟수가 크게 줄어들어 속도가 빨라집니다. 구현 절차는 다음과 같습니다.

• 검사 대상 숫자의 제곱근을 구합니다.
• 2부터 제곱근(내림한 값)까지 차례대로 나누어 나머지가 생기는지 확인합니다.
• 중간에 한 번이라도 나머지가 0이 되면 그 수는 소수가 아닙니다.

예제 코드

import math
import time

def is_prime(final_val):
    # 1은 소수가 아님
    if final_val <= 1:
        return False
    i = 2
    while i <= math.isqrt(final_val):
        # 나누어 떨어지는지 확인
        if final_val % i == 0:
            return False
        i += 1
    return True

# 시작 시간 기록
start_time = time.time()

cnt = 0
for n in range(1, 10001):
    cnt += is_prime(n)

print('10000까지의 소수 개수:', cnt)

# 종료 시간 기록
end_time = time.time()
print('소요 시간:', end_time - start_time)

실행 결과

10000까지의 소수 개수: 1229
소요 시간: 약 0.053초

모든 약수를 검사하는 첫 번째 방법보다 약 40배 이상 빠른 결과를 확인할 수 있습니다. 참고로 파이썬 3.8 이상에서는 math.isqrt()를 사용해 부동소수점 오차 없이 정확한 정수 제곱근을 구할 수 있습니다.

방법 3: 에라토스테네스의 체(Sieve of Eratosthenes)

이 방법은 소수를 하나씩 찾는 것이 아니라, 반대로 합성수(소수가 아닌 수)를 걸러내어 특정 범위까지의 모든 소수를 한꺼번에 구하는 고전적인 알고리즘입니다. 절차는 다음과 같습니다.

• 2부터 구하고자 하는 최대 숫자까지 연속된 정수 목록을 만듭니다.
• 목록에서 남은 가장 작은 수(처음에는 2)를 소수로 확정하고, 그 수의 배수들을 목록에서 제거합니다. 단, 그 수 자체는 제거하지 않습니다. 같은 방식으로 3, 5, 7…에 대해 반복합니다. 예를 들어 5와 11은 지워지지 않지만, 그 배수인 10과 22는 제거됩니다.
• 모든 제거 과정이 끝난 후 남은 수들이 바로 요청한 범위까지의 소수 목록입니다.

예제 코드

import time

def sieve_method(n):
    # 이미 제거된(합성수) 숫자를 담는 리스트
    removed = []
    primes = []
    for i in range(2, n + 1):
        # 합성수 목록에 없다면 소수
        if i not in removed:
            primes.append(i)
            # 자기 자신은 남기고 배수만 제거
            for j in range(i * i, n + 1, i):
                removed.append(j)
    return primes

# 시작 시간 기록
start_time = time.time()

result = sieve_method(25)
print(result)

# 종료 시간 기록
end_time = time.time()
print('소요 시간:', end_time - start_time)

실행 결과

[2, 3, 5, 7, 11, 13, 17, 19, 23]
소요 시간: 0.0초 (매우 짧음)

세 가지 방법의 성능 비교

측정 결과, 10,000까지의 소수를 구할 때 모든 약수를 검사하는 방법은 약 2.31초가 걸린 반면, 제곱근까지만 검사하는 방법은 약 0.053초로 실행 시간이 크게 단축되었습니다. 에라토스테네스의 체는 특정 범위까지의 모든 소수를 한 번에 구할 때 가장 효율적이므로, 문제의 성격에 맞는 알고리즘을 선택하는 것이 중요합니다.