エラトステネスの篩

Ruby でやってる人がいたので Python でやってみた。

cf. エラトステネスの篩 － Mae向きな日記

以前 Haskell でやったことがあるんだけどすっかり忘れててちょっと苦労したよ。
最初に書いたのはこのコード。1,000,000までの素数を列挙している。素直というか素朴というか力技。

def prime_list(n):
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        lis = [x for x in lis if x % p != 0]


primes = prime_list(1000000)

for i in primes:
    print i

ところが答えはあってるみたいだけどやたらと遅い。正確には計ってないけど4分半くらいかかる。
で、以前の Haskell のコードを見ながら改良したのがこれ。

def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = prime_list(1000000)

for i in primes:
    print i

篩にかけるのを1,000,000の二乗根までに限っている。それ以上は篩にかけても意味がないからね。これを思い出すまでに時間がかかってしまった。 で、結果はといえば劇的に速くなって約4秒程度。こんなに違うとは。