에라토스테네스의 체
는 소수를 찾는 방법이다.
고대 그리스 수학자 에라토스테네스가 발견하였다.
위 그림처럼 에라토스테네스의 체를 통해 소수를 구하는 방법은 아래와 같다.
그림의 경우, 11^2
> 120
이므로 11보다 작은 수의 배수들만 지워도 충분하다.
즉, 에라토스테네스의 체
는 소수를 구해야 하는 구간의 수 가운데 최대 범위 수의 제곱근
보다 작은 소수의 배수를 지우고 남는 수는 모두 소수이다.
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]
M, N = map(int, input().split())
N += 1
sieve = [True] * N
for i in range(2, int(N**0.5)+1):
if sieve[i]:
for j in range(2*i, N, i):
sieve[j] = False
for i in range(M, N):
if i > 1:
if sieve[i]:
print(i)