2015-07-01

エラトステネスの篩

エラトステネスの篩のPythonバージョンについて調べてみました。 下記のコードはシンプルですが、十分速いです。

下記リンク先のものと同じですが、コメント等を追加して修正しています。

エラトステネスの篩（Python編）

# -*- coding: utf-8 -*-
import math

def sieve(n):
    # 2, 3, 5とその倍数は、あらかじめ除去しておく
    blist = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(n)]
    blist[0] = blist[1] = False
    blist[2] = blist[3] = blist[5] = True
    sqrt = math.sqrt(n)

    for odd in range(7, n, 2):  # 7以上の倍数を対象とする
        if odd >= sqrt:  # エラトステネス ステップ3
            return [i for i, b in enumerate(blist) if b is True]

        for s in range(odd ** 2, n, odd):  # 除去する倍数に関して、二乗から開始する
            blist[s] = False

if __name__ == '__main__':
    n = 2000000  # 2百万の素数
    plist = sieve(n)
    print(len(plist))
    print(sum(plist))