Python에서 소수를 찾는 다양한 방법과 실행 시간 비교하기

이 튜토리얼에서는 Python으로 소수(prime number)를 찾는 여러 가지 방법을 살펴보고, 각 방법이 얼마나 많은 시간을 소요하는지 직접 측정해 비교해 보겠습니다. 실행 시간은 파이썬의 내장 time 모듈을 사용해 계산합니다.

방법 1: 기본적인 완전 탐색

가장 일반적이고 직관적인 소수 판별 방법입니다. 동작 원리는 다음과 같습니다.

• 숫자가 1보다 작거나 같으면 False를 반환합니다.
• 반복문을 돌며 어떤 수로든 나누어 떨어지면(약수가 존재하면) False를 반환합니다.
• 모든 반복을 마칠 때까지 약수가 없다면 True를 반환합니다.

예제 코드

# time 모듈 임포트
import time

# 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False
    else:
        for i in range(2, n):
            # 약수인지 확인
            if n % i == 0:
                return False
        return True

# 시작 시간 기록
start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1

print(f'범위 내 총 소수 개수: {primes}')

# 종료 시간 기록
end_time = time.time()
print(f'실행 시간: {end_time - start_time}')

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻습니다.

범위 내 총 소수 개수: 9594
실행 시간: 63.1301212310791

약 63초라는 상당히 긴 시간이 걸렸습니다. 모든 수에 대해 2부터 n-1까지 전부 검사하기 때문에 비효율적입니다.

방법 2: 제곱근까지만 검사하기

두 번째 방법은 반복 범위를 n의 제곱근까지로 줄여 반복 횟수를 크게 감소시킵니다. 수학적으로 n이 소수가 아니라면, 반드시 √n 이하의 약수를 가진다는 성질을 이용한 것입니다. 예를 들어 36의 경우, 36 = 4 × 9처럼 약수 쌍 중 하나는 반드시 √36 = 6 이하입니다.

예제 코드

# time 모듈 임포트
import time

# sqrt 함수 사용을 위한 math 모듈 임포트
import math

# 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False
    else:
        # n의 제곱근까지 반복
        for i in range(2, int(math.sqrt(n)) + 1):
            # 약수인지 확인
            if n % i == 0:
                return False
        return True

# 시작 시간 기록
start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1

print(f'범위 내 총 소수 개수: {primes}')

# 종료 시간 기록
end_time = time.time()
print(f'실행 시간: {end_time - start_time}')

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻습니다.

범위 내 총 소수 개수: 9592
실행 시간: 0.2039644718170166

무려 약 300배 이상 빨라진 것을 확인할 수 있습니다!

방법 3: 짝수 검사 생략하기

앞선 방법에서는 짝수도 함께 검사했습니다. 하지만 우리는 2를 제외한 모든 짝수는 소수가 될 수 없다는 사실을 알고 있습니다. 따라서 이번 방법에서는 짝수를 미리 걸러내어 실행 시간을 더욱 단축합니다.

예제 코드

# time 모듈 임포트
import time

# sqrt 함수 사용을 위한 math 모듈 임포트
import math

# 소수 판별 함수
def is_prime(n):
    # 1 이하인 경우
    if n <= 1:
        return False
    # 2인 경우
    elif n == 2:
        return True
    # 2보다 큰 짝수인 경우
    elif n > 2 and n % 2 == 0:
        return False
    else:
        # 홀수만 검사하며 n의 제곱근까지 반복
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            # 약수인지 확인
            if n % i == 0:
                return False
        return True

# 시작 시간 기록
start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1

print(f'범위 내 총 소수 개수: {primes}')

# 종료 시간 기록
end_time = time.time()
print(f'실행 시간: {end_time - start_time}')

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻습니다.

범위 내 총 소수 개수: 9592
실행 시간: 0.10342741012573242

검사 대상을 홀수로 한정함으로써 방법 2보다 약 2배 더 빠른 성능을 보여줍니다.

결론 및 성능 요약

세 가지 방법의 실행 시간을 정리하면 다음과 같습니다.

알고리즘을 조금만 최적화해도 성능이 수백 배 향상될 수 있다는 점이 흥미롭습니다. 참고로, 더 큰 범위의 소수를 구할 때는 에라토스테네스의 체(Sieve of Eratosthenes)와 같은 알고리즘이 훨씬 효율적이므로 추가로 학습해 볼 만합니다.

튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.