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

ami_GS's diary

情報系大学院生の備忘録。ネットワークの勉強にハマっています。

素数を計算しようのコーナー

アルゴリズム Python 検証

こんにちは、プログラムと言えば素数ですね(?)

今回は素数を求めるプログラムの処理速度を見ていこうと思います。
ある数までの素数のリストを返すプログラムを書きます。3タイプ書きましょうかね

まずはスタンダード、

import sys
import time

s = time.time()
prime = [2,3]

N = int(sys.argv[1]) #Nまでの素数を求める 

for i in range(5, N, 2):
    primeFlag = True#素数かどうかのフラグ
    for p in prime:
        #ある数 i を、すでに求めた素数で割っていく
        if p > i**0.5:
            break #ある数 i はその数のルート以下でないと割り切れない(素数である)
        elif i % p == 0:
            primeFlag = False #割れたらフラグを変えてブレーク
            break
    if primeFlag:
        prime.append(i) #最後まで i が割られなければ素数

print prime, len(prime), time.time()-s

[素数 プログラム 求め方]で検索して出てくる中でも速い方のアルゴリズム(自惚れ)。
ポイントは

  • i を5から2ずつインクリメントしていく(2の倍数は明らかに素数ではない)
  • i を素数で割っていく

てところ。


インデックスを使うタイプ

import sys
import time

s = time.time()
N = int(sys.argv[1])
prime = [True]*N #Nまでのbooleanリストを確保

prime[0], prime[1] = False, False #0及び1は素数ではない

for i in range(2, int(N**0.5)):
    if prime[i]:
        #prime[i]がTrue <=> prime[i]は素数
        for j in range(i*2, N, i):
            prime[j] = False #prime[i]の倍数は素数ではないのでFalse

ans =  [i for i in range(N) if prime[i] == True] #Trueのインデックスをリストに詰める
print len(ans), time.time()-s

これは配列に素数自体を入れるのではなくて素数かどうかの判定を入れるタイプ。
知っている中では一番速いです。

上記の物を改善したタイプ

この記事を書くにあたって色々検証していたら速度が改善されたタイプ

import sys
import time

s = time.time()
N = int(sys.argv[1])
prime = [1]*N #True, Falseを1と0で表す

prime[0], prime[1] = 0, 0

for i in range(2, int(N**0.5)):
    if prime[i]:
        for j in range(i*2, N, i):
            prime[j] = 0

ans =  [i for i in range(N) if prime[i] == 1]
print len(ans), time.time()-s

単純にTrueを1、Falseを0にしたもの

処理速度検証

処理に何秒かかるか見てみましょう
(平均時間ではないですごめんなさい)

N=1000 10000 100000 1000000 10000000 100000000
スタンダード 0.0007 0.0129 0.1941 3.6563 72.5489 やりたくない
インデックス 0.0003 0.0044 0.0479 0.4467 4.6580 54.7391
上の改善 0.0002 0.0031 0.0307 0.3998 3.7079 46.4890

とまぁこんな感じでした。
素数だけに言える事じゃなくて、インデックスを使うタイプの処理はなかなか速い(適当)
もっと速いアルゴリズム知っている方いたら教えてください。。