読者です 読者をやめる 読者になる 読者になる

Pythonでエラトステネスの篩

Project Euler の問題を解いていて、面白かったので記事にしてみました。
エラトステネスの篩 っていうのがあります。与えられた自然数より小さい素数を列挙するやつです。とりあえず書いてみたのがこれ(n≧3 を仮定)。

def furui(n):
    primes = [2]
    ls = xrange(3, n + 1 ,2)
    while ls:
        p = ls[0]
        if p > math.sqrt(n):
            primes += ls
            break
        primes.append(p)
        ls = filter(lambda x: x % p, ls)
    return primes

素直な実装(な気がする)。ところが、これが激烈に遅い。問題では200万以下の素数を全部求めないといけないんだけど、furui(2000000)は、うちの環境で23秒かかる。
一方、Project Euler: Python solutions に載っていたのはこんなコード。

def mark(s, x):
    for i in xrange(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in xrange(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in xrange(0,n) if s[i] and i > 1]

こっちはsieve(2000000)でも2秒で走る。
複雑なリスト操作(filterとか)を毎回やってないから早いんだろうな。きっと。