素数を無限に列挙するジェネレータ

エラトステネスの篩を応用して書いてみた。

import sys
import itertools

def primes():
    p = []
    p.append(2)
    yield 2
    p.append(3)
    yield 3
    for n in itertools.count(6, 6):
        n1 = n - 1
        for x in p:
            if n1 % x == 0:
                break
            else:
                p.append(n1)
                yield n1
               n2 = n + 1
               for y in p:
                   if n2 % y == 0:
                       break
                   else:
                       p.append(n2)
                       yield n2

n = int(sys.argv[1])
for p in primes():
    if p < n:
        print p
    else:
        break

^o^ > python primes3.py 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

ここでは100未満の素数を出力している。さすがに primes3.py 1000000 とかやると遅い。