개념
에라토스테네스의 체는 구간에서 여러 개의 수가 소수인지 아닌지를 판단할 때 유용한 알고리즘입니다. 에라토스테네스의 체를 사용하기에 앞서 소수의 성질을 살펴보겠습니다.
1부터 10까지의 숫자가 있을때 즉 다음과 같을 때 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 소수는 1을 제외한 수들 중 약수가 자기 자신과 1만 존재하는 수입니다. 따라서 2, 3, 5, 7이 소수입니다.
에라토스테네스의 체알고리즘의 과정은 다음과 같습니다.
1. 2부터 N까지 자연수를 나열한다.
2. 숫자들 중 아직 처리하지 않은 수를 찾는다.
3. 그 숫자의 배수들을 제거한다. 단 2 배수부터 제거한다. (2나 3이 제거되는 것을 방지)
4. 위의 2, 3, 과정을 반복한다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
import math
# 1부터 100까지의 소수를 모두 찾는 에라토스테네스의 체
n = 100
array = [True] * (1 + n)
for i in range(2, int(math.sqrt(n) + 1)):
if array[i] == True: # 아직 처리되지 않은 숫자인 경우
j = 2
while i * j <= n:
array[i * j] = False
j += 1
for i in range(2, n+1):
if array[i] == True:
print(i, end=" ")
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 다익스트라 알고리즘 (Python) (0) | 2020.12.22 |
|---|---|
| 편집거리 알고리즘 (Python) (0) | 2020.12.22 |
| 가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python) (0) | 2020.12.19 |
| 이진탐색 (Python) (0) | 2020.12.16 |
| bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python) (0) | 2020.12.15 |