에라토스테네스의 체 Sieve of Eratosthenes 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 마치 체로 치듯 수를 걸러내가며 소수를 찾아가는 방법 특정 범위 내의 소수를 찾는 방법 완전 탐색(일종의 노가다 방식)이라 무식한 방법이지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우 이보다 빠른 방법이 없음. 다만, '특정 범위 내의 소수'를 판정하는 데에만 효율적 소수 Prime Number 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 2, 3, 5, 7, 11, ... 방법 범위 내의 모든 수 나열 소수도, 합성수도 아닌 1부터 제거 2부터 차례대로 소수인 n의 배수를 모두 제거 주어진 범위가 k라면 √k보다 작은 소수들에 한하여 3.의..