"エラトステネスの篩"の書き方いろいろ - 比較

このエントリーは遥かに途中です。

概要

CodeJamJapan2011の練習問題Bで10^12までの素数求める必要があり、最初に書いたO(n^2)のアルゴリズムでは、とても計算が終わらなかったので、高速に素数を求めるためのアプローチとして有名なエラトステネスの篩という有名なアルゴリズムを知らなかったので調べたりやってみたことをエントリー。書き方でいろいろと実行時間がじ結局10^12の壁が乗り越えられなかったエントリー。

いろいろと書いてみた, ネットで調べてみた.

基本のアルゴリズム

ジェネレータを使った素数を求める一般的なアルゴリズム.

def get_primes(N):
    n = 2
    while n <= N:
        i = 2
        while i < n:
            if n % i ==0:
                break
            i += 1
        if i == n:
            yield n
        n += 1

再起でやるエラトステネスの篩

関数ints()は無限リストのジェネレーターを作るための関数.

def sieve(L):
    head = L.next()
    yield head
    for e in sieve(x for x in L if x % head != 0):
        yield e

def ints(min, max):
    n = min
    while n < max:
        yield n
        n += 1

再起しないエラトステネス(自分で書いたやつ)

def my_sieve(N):
    L = ints(2, N+1)
    head = L.next()
    PL = [head, ]
    while(pow(head, 2) < N):
        L = iter([x for x in L if x % head != 0])
        head = L.next()
        PL.append(head)
    return PL + list(L)

再起しないエラトステネス2, ネットで拾ってきたやつスクリプト

def eras(N):
    siv = range(N+1)
    siv[1] = 0
    sqn = int(round(N**0.5))
    for i in range(2, sqn+1):
        if siv[i] != 0:
                siv[2*i:N/i*i+1:i] = [0] * (N / i - 1)
    return filter(None,siv)