『エラトステネスの篩』の記述例（Python版）

元記事より分離しました．アルゴリズム等は元記事を御参照下さい．趣旨は元記事と同じく『「エラトステネスの篩」だとこれだけ速く素数が求まる！』ですが，ライブラリ等によってよりシンプルな記述表現がある場合など，他のプログラミング言語との比較を避けるため，個別記事としている次第です．特にPythonについては，現状で標準ライブラリと化しているNumPyを用いる場合とそうでない場合とで，記述表現や処理速度に大きな違いが出ています．

記述例および実行例（NumPy未使用その１）

sieve.py

x = int(input())
a = [True] * (x+1)
a[1], r = False, []

for i in range(1, x+1):
    if a[i]:
      if i <= x**0.5:
        for j in range(i*i, x+1, i):
          a[j] = False
      r += [i]

print(len(r))
print(r[-1])

次の実行環境にて，百万までの素数の個数と最大の素数を表示しています．

• ASUS Zenfone 5: Qualcomm Snapdragon 636 1.8GHz, 6GBメモリ
• Android 9 + Termux + AnLinux(Debian GNU/Linux 10) + Python 3.7.3

$ time python3 sieve.py <<< 1000000
78498
999983

real    0m1.268s
user    0m0.970s
sys     0m0.050s

記述例および実行例（NumPy未使用その２）

sieve2.py

x = int(input())
a = [True] * (x+1)
a[0] = a[1] = False

for i in range(1, int(x**0.5) + 1):
    if a[i]: a[i*i::i] = [False] * (x//i - i + 1)
r = [i for i, p in enumerate(a) if p]

print(len(r))
print(r[-1])

上記と同じ次の実行環境にて，一千万までの素数の個数と最大の素数を表示しています．

• ASUS Zenfone 5: Qualcomm Snapdragon 636 1.8GHz, 6GBメモリ
• Android 9 + Termux + AnLinux(Debian GNU/Linux 10) + Python 3.7.3

$ time python3 sieve2.py <<< 10000000
664579
9999991

real    0m2.657s
user    0m2.270s
sys     0m0.290s

記述例および実行例（NumPy使用）

sieve.py

from numpy import ones, sqrt, arange

x = int(input())
a = ones(x+1, dtype=bool)
a[0:2] = False

for i in range(2, int(sqrt(x))+1):
    if a[i]: a[i*i::i] = False
r = arange(x+1)[a]

print(len(r))
print(r[-1])

上記と同じ次の実行環境にて，一億までの素数の個数と最大の素数を表示しています．

• ASUS Zenfone 5: Qualcomm Snapdragon 636 1.8GHz, 6GBメモリ
• Android 9 + Termux + AnLinux(Debian GNU/Linux 10) + Python 3.7.3

$ time python3 sieve-numpy.py <<< 100000000
5761455
99999989

real    0m6.163s
user    0m5.010s
sys     0m1.940s

備考

更新履歴

• 2022-01-17：NumPyなし記述例その２追加（コメントより）
• 2022-01-17：元記事より移行