에라토스테네스의 체 알고리즘
- 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때
- 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘
- 에라토스테네스의 체 알고리즘의 구체적인 동작 과정
- 1) 2부터 N까지의 모든 자연수를 나열한다.
- 2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
- 3) 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않음 !)
- 4) 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.
에라토스테네서의 체 알고리즘 동작 예시
- 1) 2부터 N까지의 모든 자연수를 나열한다.
- 2) 아직 처리하지 않은 가장 작은 수 2를 제외한 2의 배수는 모두 제거한다
- 3) 아직 처리하지 않은 가장 작은 수 3을 제외한 3의 배수는 모두 제거한다.
- 4) 아직 처리하지 않은 가장 작은 수 5를 제외한 5의 배수는 모두 제거한다
- 5) 마찬가지의 과정을 반복했을 때 최종적인 결과는 다음과 같다.
에라토스테네스의 체 알고리즘 (Python)
import math
# 2부터 1000까지의 모든 수에 대하여 소수 판별
n = 1000
# 모든 수가 소수 (True)인 것으로 초기화
array = [True for i in range(n+1)]
# 에라토스테네스의 체 알고리즘
# 2부터 n의 제곱근까지의 모든 수를 확인
for i in range(2, int(math.sqrt(n) + 1) :
# i가 소수인 경우
if array[i] == True :
# i를 제외한 i의 모든 배수 지우기
j = 2
while i*j <= n :
array[i*j] = False
j += 1
# 남은 모든 소수 출력
for i in range(2, n+1) :
if array[i] :
print(i, end=' ')
에라토스테네스의 체 알고리즘 성능분석
- 시간 복잡도 : 선형 시간에 가까울 정도로 매우 빠르다. (O(NloglongN))
- 다수의 소수를 찾아야 하는 문제에 효과적으로 사용될 수 있다.
예제 문제
- 백준 4948번 (베르트랑 공준)
- 백준 17103번 (골든바흐 파티션)
'Python > 자료구조, 알고리즘' 카테고리의 다른 글
[파이썬] 약수, 배수, 소수 (0) | 2023.04.03 |
---|---|
집합과 맵 (0) | 2023.04.02 |
재귀함수 (1) | 2023.02.03 |