효율적인 소수 찾기: 에라토스테네스의 체

소수란 1과 자기 자신만으로 나누어 떨어지는 자연수를 말한다. 에라토스테네스의 체는 다음과 같은 단계로 소수를 찾는다

1. 초기 설정: 2부터 원하는 최대 숫자까지의 모든 자연수를 나열한다.
2. 소수 기준 배수 제거:
   • 처음으로 2를 선택하고, 2의 배수(4, 6, 8, ...)를 모두 지운다.
   • 다음 소수인 3을 선택하고, 3의 배수(6, 9, 12, ...)를 지운다.
   • 이 과정을 계속 반복하여 소수의 배수를 모두 지운다.
3. 종료 조건: 선택한 소수가 N제곱근에 도달하면 반복을 종료한다. 이때 남아 있는 숫자들은 모두 소수다.

에라토스테네스의 체는 시간 복잡도가 O(nlog(log(n))) 로, 소수를 찾는 데 있어 매우 효율적이다. 다른 소수 찾기 알고리즘, 예를 들어 소수 판별법에 비해 속도가 빠르기 때문에 대규모 소수 검색에 적합하다.

하지만 큰 소수 하나를 판별하는데에는 효율적이지 못하다

 

백준 1929번을 풀며 에라토스테네스의 체에 대해 공부하였다. 내가 하던 방식인 모든 수로 나눠서 판별하는 방법으로는 시간초과에 걸렸다

from collections import deque
import sys

# N과 M을 입력받는다. N은 시작 숫자, M은 끝 숫자.
N, M = map(int, sys.stdin.readline().split())

# 0부터 M까지의 숫자가 소수인지 여부를 저장하는 리스트
is_prime = [True] * (M + 1)
is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아니므로 False로 설정

# 2부터 sqrt(M)까지 반복
for i in range(2, int(M ** 0.5) + 1):
    if is_prime[i]:  # i가 소수인 경우
        # i의 배수들을 False로 설정 (소수가 아님)
        for j in range(i * i, M + 1, i):
            is_prime[j] = False
    
# 소수 리스트 초기화
prime_numbers = []

# N부터 M까지의 숫자 중에서 소수를 찾는다.
for i in range(N, M + 1):
    if is_prime[i]:  # i가 소수인 경우
        prime_numbers.append(i)  # 소수 리스트에 추가

# 소수 리스트를 한 줄씩 출력
print(*prime_numbers, sep='\n')