에라토스테네스의 체(Eratosthenes' sieve )

에라토스테네스의 체(Eratosthenes' sieve )

그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법이다.

 

에라토스테네스의 체 알고리즘

1.  1부터 n까지의 자연수를 전부 나열한다.

2. 소수도, 합성수도 아닌 1을 지운다.

3. 남아 있는 자연수 중 가장 작은 수인 2 의 배수들을 모두 지운다.

출처 : https://terms.naver.com/entry.naver?docId=3405213&cid=47324&categoryId=47324

4. 남아 있는 자연수 중 가장 작은 수인 3의 배수들을 모두 지운다.

출처 : https://terms.naver.com/entry.naver?docId=3405213&cid=47324&categoryId=47324

5. 남아 있는 자연수 중 가장 작은 수는 소수다. 이 수의 배수들을 모두 지운다.

6. 남은 자연수 중 가장 작은 수가 n의 제곱근을 넘을 때까지 과정 5를 반복하면, 남아 있는 수가 모두 소수다.

 

 

코드로 표현하기(Python)

number = [False, False] + [True] * n
answer = []

for i in range(2, n+1) :
  if number[i] :
    answer.append(i)
    for j in range(i*i, n+1, i) :
      number[j] = False

* set 활용하는 방법

num = set(range(2, n+1))

for i in range(2, n+1):
  if i in num:
    num -= set(range(i*i, n+1, i))

 

 

---

 

참조

https://terms.naver.com/entry.naver?docId=1179083&cid=40942&categoryId=32204 

https://terms.naver.com/entry.naver?docId=3405213&cid=47324&categoryId=47324