[이론] 에라토스테네스의 체

에라토스테네스의 체 작동 방식

채로 걸러내는 것과 같이 어떤 수가 소수로 판정되면 어떤 수에 1을 제외한 나머지 수를 곱한 것은 모두 합성수이기 때문에 이들을 모두 제거하고 남아있는 수 중 다음으로 작은 수에 1을 제외한 나머지 수를 곱한 값들을 제거한다. 이를 계속

반복하면 남아있는 것들은 모두 소수이다.