素数列の生成3

素数列の生成2 - 銀月の符号 を微修正。3 以上の奇数の生成方法を itertools.islice(itertools.count(3), 0, None, 2) に変更。うちの実行環境 CPython 2.6.4 on Win32 ではこちらのほうが早かった。 CPython 全般でこちらのほうが早いと予想しているが Jython, IronPython でどうかは見当つかず。あと CPython でも長整数の領域に入ったとき、遅いような気がするが、未確認。

prime.py

# coding: utf-8

u"""素数列の生成 - 遅延評価によるエラトステネスの篩
"""

import itertools

def prime_numbers():
    u"""素数列"""

    yield 2
    odds = itertools.islice(itertools.count(3), 0, None, 2)
    sequences = {4: 2}
    sequences_pop = sequences.pop
    for i in odds:
        d = sequences_pop(i, None)
        if d is None:
            yield i
            i, d = i ** 2, i * 2
        else:
            i += d
            while i in sequences:
                i += d
        sequences[i] = d

def main():
    import sys
    from itertools import takewhile

    max_ = int(sys.argv[1]) if len(sys.argv) > 1 else 30
    for i, prime in enumerate(
            takewhile(lambda x: x < max_, prime_numbers())):
        print i, prime

if __name__ == '__main__':
    main()

実行結果

>prime.py 30
0 2
1 3
2 5
3 7
4 11
5 13
6 17
7 19
8 23
9 29