그랬었습니다

이 문제는 아래의 "알고리즘 분류"에 힌트가 있다. 에라토스테네스의 체. 간단히 설명하면, 2를 제외한 2의 배수를 소수의 후보에서 제외하고, 3을 제외한 3의 배수를 소수의 후보에서 제외, (4는 후보에서 제외되었으니 5를 제외한 5의 배수를 소수의 후보에서 제외.. 와 같은 식으로 원하는 범위까지의 소수를 구하는 방법이다. 근데 만약 100까지의 소수를 구한다고 가정하면, 굳이 2부터 100까지 1씩 늘려가며 모두 배수를 검사할 필요가 없다. 100의 절반인 50부터는 검사를 하나마나 남아있는 후보들의 배수는 범위 안에 없기 때문이다. 그러므로 최대 범위의 절반까지 배수를 구하면서 후보를 제외한다. 아래가 그 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..