エラトステネスのふるい

素数を列挙するエラトステネスの篩（ふるい）をプログラムしてみましょう。

集合を使う

例えば1000未満の素数は集合ですので，Python の集合を使ってみます。Python の集合は，例えば

s = {2, 3, 5, 7}

のように打ち込むと作れます。集合に要素を加えたり削除したりするには

s.add(9)    # 追加
s.remove(2) # 削除

のようにします。

まずは 2 以上 n 未満の整数の集合 prime を作りましょう：

n = 1000
prime = {i for i in range(2, n)}

2 以上 n 未満の整数 i について，もし i が prime に入っているなら，その倍数を prime から削除します：

for i in range(2,n):
    if i in prime:
        for j in range(i*2, n, i):
            if j in prime:
                prime.remove(j)

対話型環境なら，中身を調べてみましょう：

In [ ]: max(prime)
Out[ ]: 997

In [ ]: min(prime)
Out[ ]: 2

In [ ]: len(prime)
Out[ ]: 168

In [ ]: 23 in prime
Out[ ]: True

In [ ]: 24 in prime
Out[ ]: False

リストを使う

リストは配列に相当するものです。例えば10未満の素数を列挙する場合，

prime = [2, 3, 5, 7]

のように集合と同じようにリストを使う方法と，

prime = [False, False, True, True, False, True, False, True, False, False]

のように真偽値の並びで prime[i] が True なら i は素数だとする方法があります。ここでは後者の方法を使います。

まず prime[0] と prime[1] だけ False にして，残りは True にします：

n = 1000
prime = [False] * 2 + [True] * (n-2)

残りは集合の場合と同じですが，除去する際に，含まれているかどうかを判定する必要がありません：

for i in range(2, n):
    if prime[i]:
        for j in range(i*2, n, i):
            prime[j] = False

個数は次のようにして調べられます：

In [ ]: sum(prime)
Out[ ]: 168

集合のようなリストに変換するには次のようにします：

s = []
for i in range(2, n):
    if prime[i]:
        s.append(i)

これは次のようにも書けます：

s = [i for i in range(2, n) if prime[i]]

リストでなく集合を作るときにも同じようにできます：

s = {i for i in range(2, n) if prime[i]}

リストや集合のこのような for を使った表し方を内包表記（comprehension）と呼びます。

ndarray を使う

NumPy の ndarray を使えばもっとメモリ効率を良くできます。

import numpy as np

prime = np.ones(1000, dtype="bool")  # [True] * 1000
prime[0:2] = False                   # prime[0] = prime[1] = False

残りはリストの場合と同じです。

このように bool 型にすれば，1要素1バイトで済みます。メモリ量を調べるには次のようにします：

In [ ]: import sys

In [ ]: sys.getsizeof(prime)
Out[ ]: 1096

もっとメモリを節約するには，2 だけ特別扱いにして奇数だけ考えるなどが考えられます。

Last modified: