Problem 7

Problem 3の素数をgeneratorを使おう！と思っていたので丁度いい．さて使い方がよくわからないので調べてみた．
4 TopCoder: Python - generatorで素数生成
これ凄く短くて良いね！と思ったのもつかの間．遅いです．よく見てみたら，

ifilter(lambda x: x%prime, g)

ここが素数判定．（今までの素数で）割り切れない数を返すみたいな流れだと思う．（あんまりわかっていない）のでこれで遅いのは当たり前．

さて，これの高速化をどうするべきか？判定そのものが速ければ良い．
Pythonを使って高速素数判定をしてみる - Pashango’s Blog
まんまのがあったｗｗｗｗ

最後に実装しているのはミラー・ラビン素数判定法．以前似たようなことをしたくてWikipeidaを眺めていたことがあって，ちゃんと理解できてなかったのか上手く実装できなかった…．
さてではこれらを使って，実装を試みた．満足のいく速度になったけど，長い．エラトステネスの篩を禁じた意味があまり…．

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q-1) >> 1
    while d & 1 == 0:
        d >>= 1
    for a in [2,7,61]:
        if a > q-1:
            continue
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def next_prime():
    g = 3
    yield 2
    while True:
        if is_prime(g):
            yield g
        g += 2

primes = next_prime()
for i, prime in enumerate(primes):
    if i%10000== 0 and i > 0:
        print prime
        break

ほとんどコピーだけど，ちょっぴり違いがあるので説明しておくと決定的アルゴリズムにしている．
ミラー–ラビン素数判定法 - Wikipedia

もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。
もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である

今回の素数は恐らく,4,759,123,141以下なのでという期待のもと行った．ループ実行回数がトータルで大幅ダウンなのでかなり早くなる?
これだけだと寂しいので実行速度の比較を行ってみました．ちなみに元の50回の乱択を利用した場合と上の場合とエラトステネスの篩で必要数ぎりぎりまで指定した場合だと，エラトステネスの篩の方が速いです．

0.306564092636 sec
3.17649292946 sec
0.0391080379486 sec

上から順に，決定的を使用した場合，ミラー・ラビンを使用した場合，最後にエラトステネスの篩（使用リストの長さは105000/2)これだけだと味気ないので，10万1個目の素数(1299721)を出力させてみた時の時間も比較してみた．（使用したリストの長さは1300000/2)

3.81203198433 sec
34.3158791065 sec
0.547644853592 sec

大体10倍なので，O(n)だね！多分…．（怪しすぎるｗｗｗ)
これだけ見ているとエラトステネスの篩が良いように見えるけど，実際のところそうでもない．1万個までの素数の大きさが不明なので適切なサイズが分からない．現に10万個目の素数は上のソースから求めて適切なサイズを用意したし．それにこれは1から順に数えるという作業をいれているけど，単純に素数かどうかの判定を行うならエラトステネスの篩よりミラー・ラビンなどの方がはやい．

3.09944152832e-05 sec
0.000339031219482 sec
0.554790019989 sec

10万1個目の素数が素数かどうか判別させてみた．またリストを使用しない分メモリの節約にもなる！要するに使いどころですね．