정수 x를 선택하면, x보다 작거나 같은 모든 소수를 어떻게 찾을 수 있을까요? 에라토스테네스의 체를 이용하는 방법이 있는데, 이 방법은 고대 그리스 시대로 거상하고 있습니다. 에라토스테네스의 체를 사용하는 단계는 다음과 같습니다: 첫 번째로, 2부터 x까지의 모든 정수를 나열하고 2를 남기고 2의 배수를 모두 제거합니다. 두 번째로, 남은 수들 중에서 2에 이어지는 소수는 3입니다. 3을 남기고 3의 배수를 모두 제거합니다. 세 번째로, 3에 이어지는 소수는 5입니다. 5를 남기고 5의 배수를 모두 제거합니다. 마지막으로, 두 번째 단계에서 남은 수들 중에서 x보다 작거나 같은 가장 가까운 소수를 남기고, 이 소수의 모든 배수를 제거합니다. 그러면, 남은 수들이 바로 x보다 작거나 같은 모든 소수입니다. 위의 방법은 다음과 같은 사실을 바탕으로 합니다. 만약 a가 소수가 아니라면, a는 necessarily 의 인수를 가지고 있을 것입니다.
에라토스테네스의 체를 사용하여 소수 테이블을 더 쉽게 만들 수 있습니다. 만약 큰 정수 a(예: 10000)가 있고 소수 테이블이 없는 경우, 어떻게 신속하게 그것이 소수인지 확인할 수 있을까요? 사실, a를 나누는 모든 소수를 시도해보면 됩니다.