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とか)を毎回やってないから早いんだろうな。きっと。