エラトステネスの篩

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秒程度。こんなに違うとは。

カテゴリー: algorithm, Python パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください