素数を生成するためのふるいを作成しました。私は、プログラミングを含む RSA に関する学校のプロジェクトを行っています。素数を RSA システムに使用しますが、これは私のエッセイのためなので、セキュリティはそれほど重要ではありません。ただし、大きな素数ははるかに挑戦的であり、私はそれが好きです。私が使用するコード:
def Zeef(a):
import math
upperBound = a
upperBoundSquareRoot = int(math.sqrt(upperBound))
isPrime = [1 for m in range (0,upperBound+1)]
for m in range(2,upperBoundSquareRoot+1):
if (isPrime[m]==1):
for k in range(m*m,upperBound+1,m):
isPrime[k] = 0;
print("Priemgetallen : ")
numberofPrimes = 0
for m in range(2,upperBound+1):
if (isPrime[m] ==1):
print(m)
numberofPrimes = numberofPrimes+1
print("Aantal = " , numberofPrimes);
a=input("Alle priemgetallen tot: ")
aa=int(a)
Priemen = Zeef(aa)
素数を生成するためのより高速な方法があると確信していますが、今のところコードを改善することにあまり興味がありません。
この関数を実行すると、最大 7 桁の素数を生成するのに問題なく動作しますが、それ以上の数が必要な場合は非常に遅くなります。私のコンピュータ (8 GB RAM) は、十分なメモリがないというメッセージを表示します。別のツールである Processing でも同じアルゴリズムを使用しました。処理は非常に高速ですが、10 桁以上は認識しません。また、コンピューターが計算できる素数を生成しているときに、印刷が遅いことに気付きました。
インターネットで検索を始めたところ、プログラムをコンパイルすると進行が速くなることがわかりましたが、計算と印刷の部分が速くなるのか、解釈の部分だけが速くなるのかはわかりません。また、配列に関する numpy について何かを見つけましたが、これが私の機能を著しく高速化するかどうかはわかりません。
素数をより速く見つけるにはどうすればよいですか?