概要

エラトステネスの篩等の篩法を用いることで \(N\) 以下の全ての素数を見つけることができる。

エラトステネスの篩

エラトステネスの篩 (Sieve of Eratosthenes)

計算量

\(O(N \log \log N)\)

実装

from math import sqrt
M = 10**6
p = [1]*(M+1)
p[0] = p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

Verified

  • AOJ: "0009 - Prime Number": source (Python3, 0.55sec)

アトキンの篩

アトキンの篩 (Sieve of Atkin)

計算量

\(\displaystyle O \left( \frac{N}{\log \log N} \right)\)

実装

M = 10**6
 
p = [0]*(M+60)
sM = M**0.5
for x in range(1, int(sM/2)+1):
    v = 4*x*x + 1; y = 8
    while v <= M:
        if v % 12 != 9: # v % 12 in [1, 5]
            p[v] ^= 1
        v += y; y += 8
for x in range(1, int(sM/3**0.5)+1, 2):
    v = 3*x*x + 4; y = 12
    while v <= M:
        if v % 12 == 7:
            p[v] ^= 1
        v += y; y += 8
for x in range(2, int(sM/2**0.5)+1):
    v = 2*x*(x+1)-1; y = 4*x-8
    while 0 <= y and v <= M:
        if v % 12 == 11:
            p[v] ^= 1
        v += y; y -= 8
 
for n in range(5, int(sM)+1):
    if p[n]:
        for z in range(n*n, M, n*n):
            p[z] = 0
p[2] = p[3] = 1

Verified

  • AOJ: "0009 - Prime Number": source (Python3, 0.46sec)

参考

戻る