소수 판별: 비효율부터 최적화까지

소수 판별은 알고리즘의 중요한 개념 중 하나로, 소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 양의 정수를 의미합니다. 이번 포스팅에서는 소수를 판별하는 여러 알고리즘을 가장 단순한 방법부터 효율적인 방법까지 단계적으로 살펴보겠습니다.

 

1. 가장 단순한 방법: 나이브 접근법

가장 기본적인 소수 판별 알고리즘은 단순하게 숫자 n에 대해 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

이 방식은 이해하기 쉽지만, 비효율적입니다. 특히 n이 커질수록 반복의 횟수가 너무 많아져 계산 속도가 급격히 느려집니다. 시간 복잡도는 O(n)입니다.

 

2. 개선된 방법: 제곱근까지 검사하기

나이브 접근법의 가장 큰 문제점은 불필요한 연산이 많다는 점입니다. 실제로는 n의 제곱근까지만 검사하면 소수 여부를 판단할 수 있습니다. 예를 들어, n = 36이라면, 6보다 큰 수로는 이미 이전에 나누어진 결과를 통해 나누어지는지 확인한 것입니다.

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

이 방법은 n의 제곱근까지만 반복하므로 시간 복잡도가 O(√n)으로 줄어듭니다. 이는 이전 방법보다 훨씬 효율적입니다.

 

3. 더 나은 개선: 6의 배수 최적화

소수의 대부분은 6의 배수와 관련된 패턴을 가집니다. 2와 3을 제외하고, 모든 소수는 6k-1 또는 6k+1 형태를 가집니다. 이를 이용해 더 효율적인 소수 판별 알고리즘을 만들 수 있습니다.

import math

# 6의 배수를 활용한 소수 판별 함수
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

이 방법은 이전의 제곱근 접근법을 최적화한 것으로, i와 i + 2 두 값을 검사함으로써 불필요한 계산을 줄입니다. 시간 복잡도는 여전히 O(√n)이지만, 실제로는 반복 횟수가 줄어들어 더 빠릅니다.

 

4. 에라토스테네스의 체: 여러 수의 소수 여부 판별하기

여러 개의 숫자에 대해 소수를 판별해야 할 때는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하는 것이 효율적입니다. 이 방법은 특정 범위 내의 모든 소수를 빠르게 찾을 수 있는 알고리즘입니다.

# 에라토스테네스의 체를 이용한 소수 리스트 생성 함수
def sieve_of_eratosthenes(limit):
    primes = [True] * (limit + 1)
    p = 2
    while p * p <= limit:
        if primes[p]:
            for i in range(p * p, limit + 1, p):
                primes[i] = False
        p += 1
    return [p for p in range(2, limit + 1) if primes[p]]

# 예시: 50 이하의 모든 소수 찾기
print(sieve_of_eratosthenes(50))

이 방법은 크기가 큰 범위에서 소수를 빠르게 찾을 수 있도록 설계되었습니다. 시간 복잡도는 O(n log log n)으로 매우 효율적입니다.

 

5. 세그먼트 에라토스테네스의 체: 큰 범위에서의 소수 판별

에라토스테네스의 체보다 더 효율적인 방법 중 하나는 세그먼트 에라토스테네스의 체(Segmented Sieve of Eratosthenes)입니다. 이 알고리즘은 매우 큰 범위에서 소수를 찾고자 할 때 사용됩니다. 세그먼트 체는 기본적으로 에라토스테네스의 체를 여러 구간으로 나누어 소수를 판별하는 방법입니다.

import math

# 세그먼트 에라토스테네스의 체 함수
def segmented_sieve(limit):
    segment_size = int(math.sqrt(limit)) + 1
    primes = sieve_of_eratosthenes(segment_size)
    low = segment_size
    high = 2 * segment_size
    sieve = [True] * (segment_size)
    
    while low < limit:
        if high > limit:
            high = limit
        sieve = [True] * (high - low)

        for prime in primes:
            start = max(prime * prime, (low + prime - 1) // prime * prime)
            for j in range(start, high, prime):
                sieve[j - low] = False

        for i in range(low, high):
            if sieve[i - low]:
                print(i, end=" ")

        low = low + segment_size
        high = high + segment_size

# 예시: 100 이하의 모든 소수 찾기
segmented_sieve(100)

이 알고리즘은 메모리 사용량을 줄이면서도 큰 숫자 범위에서 소수를 찾는 데 매우 효율적입니다. 특히, 큰 n 범위에서 소수를 판별할 때 메모리 문제를 해결하고, 각 구간에 대해 병렬 처리를 사용할 수 있습니다. 시간 복잡도는 여전히 O(n log log n)이지만, 범위가 커질 때 더 효율적으로 작동합니다.

 

결론

• 나이브 접근법은 이해하기 쉽지만 매우 비효율적입니다 (O(n)).
• 제곱근 최적화는 반복 횟수를 줄여 효율성을 높였습니다 (O(√n)).
• 6의 배수 최적화는 소수의 특성을 활용해 더 적은 연산으로 소수 여부를 판별합니다 (O(√n)).
• 에라토스테네스의 체는 여러 개의 숫자에 대해 소수를 구할 때 가장 효율적인 방법 중 하나입니다 (O(n log log n)).
• 세그먼트 에라토스테네스의 체는 매우 큰 범위에서 소수를 판별할 때 메모리 효율성을 극대화할 수 있는 방법입니다.

소수 판별 문제를 해결하는 다양한 접근 방법을 소개했으니, 상황에 맞게 적절한 알고리즘을 선택해 활용해 보세요. 코드를 직접 실행해 보면서 각 방법의 효율성을 체감하는 것도 좋은 학습 방법이 될 것입니다.