에라토스테네스의 체
수 하나에 대하여 소수 인지 판정할 때는 밀러-라빈 소수판별법 같은 빠른 소수판별법을 사용하면 되지만 1부터 N 사이 같은 특정구간의 모든 소수가 필요한 경우도 존재합니다.
그럴때는 1부터 N까지 리스트를 쫙 깔아두고 그 리스트를 가지고 소수 리스트를 생성하게 됩니다.
예를 들어서 1부터 100 사이의 모든 소수를 원한다고 가정해보겠습니다.
| $1$ |
$2$ |
$3$ |
$4$ |
$5$ |
$6$ |
$7$ |
$8$ |
$9$ |
$10$ |
| $11$ |
$12$ |
$13$ |
$14$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
| $21$ |
$22$ |
$23$ |
$24$ |
$25$ |
$26$ |
$27$ |
$28$ |
$29$ |
$30$ |
| $31$ |
$32$ |
$33$ |
$34$ |
$35$ |
$36$ |
$37$ |
$38$ |
$39$ |
$40$ |
| $41$ |
$42$ |
$43$ |
$44$ |
$45$ |
$46$ |
$47$ |
$48$ |
$49$ |
$50$ |
| $51$ |
$52$ |
$53$ |
$54$ |
$55$ |
$56$ |
$57$ |
$58$ |
$59$ |
$60$ |
| $61$ |
$62$ |
$63$ |
$64$ |
$65$ |
$66$ |
$67$ |
$68$ |
$69$ |
$70$ |
| $71$ |
$72$ |
$73$ |
$74$ |
$75$ |
$76$ |
$77$ |
$78$ |
$79$ |
$80$ |
| $81$ |
$82$ |
$83$ |
$84$ |
$85$ |
$86$ |
$87$ |
$88$ |
$89$ |
$90$ |
| $91$ |
$92$ |
$93$ |
$94$ |
$95$ |
$96$ |
$97$ |
$98$ |
$99$ |
$100$ |
1은 우선 소수가 아니니까 걸러줍니다.
| $1$ |
$2$ |
$3$ |
$4$ |
$5$ |
$6$ |
$7$ |
$8$ |
$9$ |
$10$ |
| $11$ |
$12$ |
$13$ |
$14$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
| $21$ |
$22$ |
$23$ |
$24$ |
$25$ |
$26$ |
$27$ |
$28$ |
$29$ |
$30$ |
| $31$ |
$32$ |
$33$ |
$34$ |
$35$ |
$36$ |
$37$ |
$38$ |
$39$ |
$40$ |
| $41$ |
$42$ |
$43$ |
$44$ |
$45$ |
$46$ |
$47$ |
$48$ |
$49$ |
$50$ |
| $51$ |
$52$ |
$53$ |
$54$ |
$55$ |
$56$ |
$57$ |
$58$ |
$59$ |
$60$ |
| $61$ |
$62$ |
$63$ |
$64$ |
$65$ |
$66$ |
$67$ |
$68$ |
$69$ |
$70$ |
| $71$ |
$72$ |
$73$ |
$74$ |
$75$ |
$76$ |
$77$ |
$78$ |
$79$ |
$80$ |
| $81$ |
$82$ |
$83$ |
$84$ |
$85$ |
$86$ |
$87$ |
$88$ |
$89$ |
$90$ |
| $91$ |
$92$ |
$93$ |
$94$ |
$95$ |
$96$ |
$97$ |
$98$ |
$99$ |
$100$ |
짝수(즉, "$2$"의 배수)도 걸러줍니다.
단, $2$ 그 자체는 소수이므로 거르지 않습니다.
| $1$ |
$2$ |
$3$ |
$4$ |
$5$ |
$6$ |
$7$ |
$8$ |
$9$ |
$10$ |
| $11$ |
$12$ |
$13$ |
$14$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
| $21$ |
$22$ |
$23$ |
$24$ |
$25$ |
$26$ |
$27$ |
$28$ |
$29$ |
$30$ |
| $31$ |
$32$ |
$33$ |
$34$ |
$35$ |
$36$ |
$37$ |
$38$ |
$39$ |
$40$ |
| $41$ |
$42$ |
$43$ |
$44$ |
$45$ |
$46$ |
$47$ |
$48$ |
$49$ |
$50$ |
| $51$ |
$52$ |
$53$ |
$54$ |
$55$ |
$56$ |
$57$ |
$58$ |
$59$ |
$60$ |
| $61$ |
$62$ |
$63$ |
$64$ |
$65$ |
$66$ |
$67$ |
$68$ |
$69$ |
$70$ |
| $71$ |
$72$ |
$73$ |
$74$ |
$75$ |
$76$ |
$77$ |
$78$ |
$79$ |
$80$ |
| $81$ |
$82$ |
$83$ |
$84$ |
$85$ |
$86$ |
$87$ |
$88$ |
$89$ |
$90$ |
| $91$ |
$92$ |
$93$ |
$94$ |
$95$ |
$96$ |
$97$ |
$98$ |
$99$ |
$100$ |
$3$의 배수도 걸러줍니다.
단, $3$ 그 자체는 소수이므로 거르지 않습니다.
| $1$ |
$2$ |
$3$ |
$4$ |
$5$ |
$6$ |
$7$ |
$8$ |
$9$ |
$10$ |
| $11$ |
$12$ |
$13$ |
$14$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
| $21$ |
$22$ |
$23$ |
$24$ |
$25$ |
$26$ |
$27$ |
$28$ |
$29$ |
$30$ |
| $31$ |
$32$ |
$33$ |
$34$ |
$35$ |
$36$ |
$37$ |
$38$ |
$39$ |
$40$ |
| $41$ |
$42$ |
$43$ |
$44$ |
$45$ |
$46$ |
$47$ |
$48$ |
$49$ |
$50$ |
| $51$ |
$52$ |
$53$ |
$54$ |
$55$ |
$56$ |
$57$ |
$58$ |
$59$ |
$60$ |
| $61$ |
$62$ |
$63$ |
$64$ |
$65$ |
$66$ |
$67$ |
$68$ |
$69$ |
$70$ |
| $71$ |
$72$ |
$73$ |
$74$ |
$75$ |
$76$ |
$77$ |
$78$ |
$79$ |
$80$ |
| $81$ |
$82$ |
$83$ |
$84$ |
$85$ |
$86$ |
$87$ |
$88$ |
$89$ |
$90$ |
| $91$ |
$92$ |
$93$ |
$94$ |
$95$ |
$96$ |
$97$ |
$98$ |
$99$ |
$100$ |
$4$의 배수는 거를 필요가 없습니다.
$4$ 자체가 $2$의 배수라서 이미 걸러지고, $4$의 배수들도 $2$의 배수이기때문에 이미 걸러진지 오래입니다.
앞으로 $k$가 이미 걸러진 수라면, $k$의 배수도 이미 걸러져있을테니 무시해주도록 합니다.
$5$는 아직 걸러지지 않았으므로 $5$의 배수도 걸러줍니다.
단, $5$ 그 자체는 소수이므로 거르지 않습니다.
| $1$ |
$2$ |
$3$ |
$4$ |
$5$ |
$6$ |
$7$ |
$8$ |
$9$ |
$10$ |
| $11$ |
$12$ |
$13$ |
$14$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
| $21$ |
$22$ |
$23$ |
$24$ |
$25$ |
$26$ |
$27$ |
$28$ |
$29$ |
$30$ |
| $31$ |
$32$ |
$33$ |
$34$ |
$35$ |
$36$ |
$37$ |
$38$ |
$39$ |
$40$ |
| $41$ |
$42$ |
$43$ |
$44$ |
$45$ |
$46$ |
$47$ |
$48$ |
$49$ |
$50$ |
| $51$ |
$52$ |
$53$ |
$54$ |
$55$ |
$56$ |
$57$ |
$58$ |
$59$ |
$60$ |
| $61$ |
$62$ |
$63$ |
$64$ |
$65$ |
$66$ |
$67$ |
$68$ |
$69$ |
$70$ |
| $71$ |
$72$ |
$73$ |
$74$ |
$75$ |
$76$ |
$77$ |
$78$ |
$79$ |
$80$ |
| $81$ |
$82$ |
$83$ |
$84$ |
$85$ |
$86$ |
$87$ |
$88$ |
$89$ |
$90$ |
| $91$ |
$92$ |
$93$ |
$94$ |
$95$ |
$96$ |
$97$ |
$98$ |
$99$ |
$100$ |
이미 걸러진 $6$의 경우 무시해줍니다.
$7$이 아닌 $7$의 배수를 걸러줍니다.
| $1$ |
$2$ |
$3$ |
$4$ |
$5$ |
$6$ |
$7$ |
$8$ |
$9$ |
$10$ |
| $11$ |
$12$ |
$13$ |
$14$ |
$15$ |
$16$ |
$17$ |
$18$ |
$19$ |
$20$ |
| $21$ |
$22$ |
$23$ |
$24$ |
$25$ |
$26$ |
$27$ |
$28$ |
$29$ |
$30$ |
| $31$ |
$32$ |
$33$ |
$34$ |
$35$ |
$36$ |
$37$ |
$38$ |
$39$ |
$40$ |
| $41$ |
$42$ |
$43$ |
$44$ |
$45$ |
$46$ |
$47$ |
$48$ |
$49$ |
$50$ |
| $51$ |
$52$ |
$53$ |
$54$ |
$55$ |
$56$ |
$57$ |
$58$ |
$59$ |
$60$ |
| $61$ |
$62$ |
$63$ |
$64$ |
$65$ |
$66$ |
$67$ |
$68$ |
$69$ |
$70$ |
| $71$ |
$72$ |
$73$ |
$74$ |
$75$ |
$76$ |
$77$ |
$78$ |
$79$ |
$80$ |
| $81$ |
$82$ |
$83$ |
$84$ |
$85$ |
$86$ |
$87$ |
$88$ |
$89$ |
$90$ |
| $91$ |
$92$ |
$93$ |
$94$ |
$95$ |
$96$ |
$97$ |
$98$ |
$99$ |
$100$ |
빨간색이 좀 너저분 해보이니 아예 빨간색으로 칠한 부분을 삭제해주도록 하겠습니다.
| $1$ |
$2$ |
$3$ |
$\times$ |
$5$ |
$\times$ |
$7$ |
$\times$ |
$\times$ |
$\times$ |
| $11$ |
$\times$ |
$13$ |
$\times$ |
$\times$ |
$\times$ |
$17$ |
$\times$ |
$19$ |
$\times$ |
| $\times$ |
$\times$ |
$23$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$29$ |
$\times$ |
| $31$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$37$ |
$\times$ |
$\times$ |
$\times$ |
| $41$ |
$\times$ |
$43$ |
$\times$ |
$\times$ |
$\times$ |
$47$ |
$\times$ |
$\times$ |
$\times$ |
| $\times$ |
$\times$ |
$53$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$59$ |
$\times$ |
| $61$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$67$ |
$\times$ |
$\times$ |
$\times$ |
| $71$ |
$\times$ |
$73$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$79$ |
$\times$ |
| $\times$ |
$\times$ |
$83$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$89$ |
$\times$ |
| $\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$97$ |
$\times$ |
$\times$ |
$\times$ |
$8$은 이미 없어진지 오래입니다.
$9$와 $10$도 이미 없어졌습니다.
$11$의 배수를 걸러주려 했더니 이미 표에 $11$의 배수가 없습니다.
$13$의 배수도 없습니다...왜일까요?
$11$의 배수를 걸러준다는 것은 $11 \times 2$, $11 \times 3$, $11 \times 4$, ...를 걸러준다는 것인데
바꿔서 생각해보면 $2 \times 11$, $3 \times 11$, $4 \times 11$, ...이므로, $10 \times 11$까지는 이미 걸러진 것입니다.
$11 \times 11$부터 걸러야 하는데, $100$까지의 범위에서 거르기로 하였으므로 이미 끝난 셈입니다.
$N$까지의 범위에서 거르기로 했으면, $k \leq \sqrt{N}$인 $k$의 배수까지만 걸러주면 된다는 사실을 알았습니다.
소거는 이걸로 끝났고, 나머지 모두를 소수로 판정해줍니다.
| $1$ |
$2$ |
$3$ |
$\times$ |
$5$ |
$\times$ |
$7$ |
$\times$ |
$\times$ |
$\times$ |
| $11$ |
$\times$ |
$13$ |
$\times$ |
$\times$ |
$\times$ |
$17$ |
$\times$ |
$19$ |
$\times$ |
| $\times$ |
$\times$ |
$23$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$29$ |
$\times$ |
| $31$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$37$ |
$\times$ |
$\times$ |
$\times$ |
| $41$ |
$\times$ |
$43$ |
$\times$ |
$\times$ |
$\times$ |
$47$ |
$\times$ |
$\times$ |
$\times$ |
| $\times$ |
$\times$ |
$53$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$59$ |
$\times$ |
| $61$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$67$ |
$\times$ |
$\times$ |
$\times$ |
| $71$ |
$\times$ |
$73$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$79$ |
$\times$ |
| $\times$ |
$\times$ |
$83$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$89$ |
$\times$ |
| $\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$\times$ |
$97$ |
$\times$ |
$\times$ |
$\times$ |
앞에서 이야기 한 주제들을 가지고 이제 코드로 만들어봅시다.
1. 1은 소수가 아니다.
2. 2가 아닌 짝수(2의 배수)는 소수가 아니다.
3. 차례차례 걸러지지 않은 수의 배수를 거른다.
4. $k$의 배수를 거를 때는 $k \times k$부터 걸러도 된다.
5. $k$의 배수를 거를 때 $k$가 소수가 아니라면 이미 걸러져 있으니 필요가 없다.
위키백과에 굉장히 잘 짜여진 코드 가 있으니 이를 기반으로 만들어주도록 합니다.
어지간하면 이정도 코드로도 충분히 체를 사용할 수 있습니다.
물론 최적화의 여지는 있습니다.
아예 return 부분에서 짝수 부분을 없는거처럼 그냥 계산한 다음에, 맨 앞에 2만 붙여주면 됩니다.
1, 2를 넣었을 때 결과로 2가 나와버리는 약간의 미스가 있지만, 굳이 에라토스테네스의 체에 2를 넣진 않을거라고 생각됩니다.
i * i부터 판단해줘도 되므로 구간도 바꿔주도록 합니다.
return 부분에서 아에 sieve 짝수 부분이 어떻게 되든 상관하지도 않으므로 애초에 i가 짝수일 때는 계산 하지 않아도 됩니다.
i가 홀수일 때만 검사하고, i * i(홀수)부터 검사를 시작하므로 2i만큼 거리를 두고 걸러주면 홀수만 건드릴 수 있습니다.
여기서 더욱 최적화 하면 Linear-sieve (선형 체) 로 진화하는 과정도 존재합니다.
"에라토스테네스의 체"의 시간복잡도는 어떻게 될까요?
1부터 n까지 $2$의 배수는 대략 $\frac{n}{2}$번 있고, $3$의 배수는 $\frac{n}{3}$번, $\frac{n}{5}$번, $\frac{n}{7}$번, $\frac{n}{11}$번, ...
$\sqrt{n}$ 이하의 모든 소수 $p$에 대하여 $\frac{n}{p}$의 값을 다 더한 $\sum\limits_{p \in \mathbb{P}, p \leq \sqrt{n}} \frac{n}{p}$의 값이 시간복잡도일텐데, 메르텐스의 제 2 정리 에 따라 $\sum\limits_{p \in \mathbb{P}, p \leq n} \frac{1}{p} \sim \ln{\ln n}$이므로, $\sum\limits_{p \in \mathbb{P}, p \leq \sqrt{n}} \frac{n}{p} = n \times \sum\limits_{p \in \mathbb{P}, p \leq \sqrt{n}} \frac{1}{p} \sim n \ln{\ln \sqrt{n}} \sim n \ln{\ln n}$에서, 시간복잡도는 $O(n \ln{\ln n})$이라는 다소 충격적인 복잡도로 나오게 됩니다. 이때, $O(f(n))$은 란다우 표기법 이고, $\ln n$은 자연로그함수 입니다.
$n = 10^9$일 때도 $\ln{\ln n} = 3.03125...$ 정도이고, $n = 2^{64}$일 때도 $\ln{\ln n} = 3.79237...$ 정도이므로, 거의 $O(n)$으로 생각해도 좋습니다. (어차피 10억개짜리 리스트를 만들면 메모리 초과가 날 것입니다.)