[Algorithm] 에라토스테네스의 체

Algorithm in HelloMinchan

[Algorithm] 에라토스테네스의 체

(글쓴날 : 2020.03.23)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

---

 

 

에라토스테네스의 체

---

1) 에라토스테네스의 체란?

에라토스테네스의 체란 소수를 구할 때 사용되는 매우 유용한 알고리즘입니다.

소수란 1과 자신을 제외한 약수가 없는 1이 아닌 자연수를 뜻하며,

이러한 소수를 원하는 범위까지 효율적으로 구하고 싶다면 에라토스테네스의 체를 사용하시면 됩니다.

 

에라토스테네스의 체의 주요 원리는 정해진 숫자의 범위 내에서 합성수를 지우는 방식으로,

처음 1은 소수가 아니니 지우고, 남아있는 수 중 제일 작은 숫자인 2를 소수로 판별하여 2의 배수를 모두 지웁니다.

똑같이 남아있는 수 중 제일 작은 수인 3을 소수로 판별하여 3의 배수를 모조리 지우고, 이렇게 판별과 지움을 반복하다 보면 해당 범위 내에 숫자가 소수만 남아있게 됩니다.

---

2) 코드

변수 maxNum에 판별할 숫자의 범위를 할당해 주시면 되겠고,

소수인지 아닌지 체크할 리스트와 판별된 소수를 저장할 리스트 두 개를 선언해 주시면 되겠습니다.

(Python 기준입니다. 다른 언어는 배열을 선언하시면 됩니다.)

이중 for문을 통해 에라토스테네스의 체가 실행되며, 최종적으로 prime 리스트에 소수들이 저장됩니다.

 

* Python 코드

maxNum = 판별할 숫자의 범위
check = [False, False] + [True] * (maxNum - 1)
prime = []
 
for i in range(2, maxNum + 1):
    if check[i]:
        prime.append(i)
        for j in range(2 * i, maxNum + 1, i):
            check[j] = False

---