에라토스테네스의 체란? 소수를 찾는 방법으로, 고대 그리스 수학자 에라토스테네스가 발견했다. 이 알고리즘을 사용하지 않고 단순히 소수를 구하려고 할 때 시간이 오래 걸리므로 소수를 구하고자 할 때 에라토스테네스의 체 알고리즘을 사용하는 것이 훨씬 효율적이다. Alogrithm 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색으로 표시) 자기 자신을 제외한 2의 배수를 모두 지운다. (선홍색으로 표시) 남아있는 수 가운데 2의 다음인 3은 소수이므로 오른쪽에 3을 쓴다. (초록색으로 표시) 자기 자신을 제외한 3의 배수를 모두 지운다. (연초록으로 표시) 위의 과정을 반복하면 구하고자 하는 구간의 ..
