素数を見つけるためのアルゴリズム

素数を見つけるためのアルゴリズムの最適化

2 3 5 7 11 13 17 19 23 29 31 ... $ 250,000 ...

Pascalプログラミング言語の勉強を始めたのは、大学の昔で、宿題は素数を見つけるためのアルゴリズムを作成することでした。

このアルゴリズムは発明され、研究対象の言語で実装されました。 プログラムはユーザーに数Nを求め、Nまでのすべての素数を探しました。 最初の成功したテストの後、N =「多く」を導入するための抵抗できない欲求がすぐに生じました。 プログラムは機能しましたが、私たちが望むほど速くはありませんでした。 当然、問題は多数のチェック（N * N / 2のオーダー）で行われたため、不要なチェックを削除する必要がありました。 その結果、5つの同様のアルゴリズムが判明し、それぞれが以前のアルゴリズムよりも高速に機能しました。 最近、それらを覚えて実装したかったのですが、今回はPythonでした。

行きましょう。 学生の頭に当たる最初のアルゴリズムをリスト1に示します。

#  1 #  N n = input("n=") #        lst = [] #  k     k = 0 #     2  N for i in xrange(2, n+1): #     2   for j in xrange(2, i): #    if i % j == 0: k = k + 1 #   ,     if k == 0: lst.append(i) else: k = 0 #     print lst 

各数の約数を数える必要がないため、変数kをその義務から解放できることがすぐにわかります。 実際、少なくとも1つの除数が存在する場合、その数は素数ではなくなります。 リスト2を参照してください。

 #  2 n = input("n=") lst = [] for i in xrange(2, n+1): for j in xrange(2, i): if i % j == 0: #   ,   . break else: lst.append(i) print lst 

breakコンストラクトを使用すると、内側のループを完了し、外側のループの次の反復に進むことができます。
その後、「なぜ数値が2で割り切れないのに4で割るのか？」という疑問が生じます。 配当を超えない素数間でのみ除数を検索する必要があると判断します。 アルゴリズムが...リスト3を参照してください。

 #  3 n = input("n=") lst=[] for i in xrange(2, n+1): #    (lst)   for j in lst: if i % j == 0: break else: lst.append(i) print lst 

そして、数字の理論を思い出し、求められているルートを超えない数字だけを整理する必要があることを理解します。 たとえば、数値Mに除数piがある場合、pi * qi = Mとなる除数qiがあります。つまり、ペアを見つけるには、小さい方を見つけるだけで十分です。 すべてのペアの中で、最小の予想されるペアは、piとqiが等しいペアです。つまり、pi * pi = M => pi = sqrt（M）です。 リスト4を参照してください。

 #  4 from math import sqrt n = input("n=") lst=[] for i in xrange(2, n+1): for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

N = 10000のリスト4のコードは、最初のオプションよりも約1000倍高速に実行されます。 別の「アクセラレータ」があり、1、3、7、または9で終わる番号のみをチェックします（残りは明らかに2または5で割り切れるので）。 リスト5を参照してください。

 #  5 from math import sqrt n = input("n=") lst=[] for i in xrange(2, n+1): if (i > 10): if (i%2==0) or (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

リスト5の小さな変更の結果、速度がわずかに向上します。

 #  6 from math import sqrt n = input("n=") lst=[2] for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

合計：最後のリストのプログラムは、元のバージョンよりも約1300倍高速に実行されます。
この問題をできるだけ早く解決するためのプログラムを作成するというタスクを自分自身に設定したわけではありません。これは、正しく構成されたアルゴリズムがプログラムの最適化に重要な役割を果たすことを初心者プログラマーに示しています。

PS
コメントのおかげで、リスト7が得られます。

 #  7 n = input("n=") lst=[2] for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j*j-1 > i: lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

N = 10000で、時間を学習します。
時間1 = 26.24
時間2 = 3.113
時間3 = 0.413
時間4 = 0.096
時間5 = 0.087
時間6 = 0.083
時間7 = 0.053

エラトステネスのふるい：

 #  8 n = input("n=") a = range(n+1) a[1] = 0 lst = [] i = 2 while i <= n: if a[i] != 0: lst.append(a[i]) for j in xrange(i, n+1, i): a[j] = 0 i += 1 print lst 

n = 1,000,000の結果：
時間7 = 7.088
時間8 = 1.143