소수 판별은 알고리즘의 중요한 개념 중 하나로, 소수는 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)).
- 세그먼트 에라토스테네스의 체는 매우 큰 범위에서 소수를 판별할 때 메모리 효율성을 극대화할 수 있는 방법입니다.
소수 판별 문제를 해결하는 다양한 접근 방법을 소개했으니, 상황에 맞게 적절한 알고리즘을 선택해 활용해 보세요. 코드를 직접 실행해 보면서 각 방법의 효율성을 체감하는 것도 좋은 학습 방법이 될 것입니다.
'알고리즘' 카테고리의 다른 글
| 2~9까지 배수 판별법 (0) | 2024.11.25 |
|---|---|
| 최대공약수(GCD)를 구하는 방법 (0) | 2024.11.21 |
| 최단경로 알고리즘 BFS, 다익스트라, 벨만-포드, 플로이드 와샬 (0) | 2022.03.24 |
| 최대 공약수 (With. 유클리드 호제법) (0) | 2021.10.28 |
