Pythonで素数判定（3） - inamori’s diary

エラトステネスのふるいの速度を確認します。まずは最も単純なもの。 def sieve1(N): a = [ True ] * (N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n])): for k in xrange(p * 2, N + 1, p): a[k] = False return [ n for n in xrange(2, N + 1) if a[n] ] t0 = time.clock() N = 10 ** 6 primes = sieve1(N) print len(primes) print time.clock() - t0 78498 0.242247248827外側のループなのでtakewhileを使ってもだいじょうぶ。 次に、2の倍数は最初から無視する方法。配