[CodingTest] 백준 1929 소수 구하기 Python, 에라토스테스의 체
🙆♂️ import 🙇♂️
에라토스테네스의 체
에라토스테네스의 체
는 소수를 찾는 방법이다.
고대 그리스 수학자 에라토스테네스가 발견하였다.
위 그림처럼 에라토스테네스의 체를 통해 소수를 구하는 방법은 아래와 같다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 11^2
> 120
이므로 11보다 작은 수의 배수들만 지워도 충분하다.
즉, 에라토스테네스의 체
는 소수를 구해야 하는 구간의 수 가운데 최대 범위 수의 제곱근
보다 작은 소수의 배수를 지우고 남는 수는 모두 소수이다.
Python 알고리즘
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)
댓글남기기