問題タブ [sieve]

数値が素数であるかどうかを確認するために反復を切り取るのは問題ですか?

元。37 は素数であり、最大 18.5 (37 の半分) と 6.08 (平方根) を比較すると、多くの作業が省略されますが、どちらも同じ原則に従っていますか?

質問してすみません、私は数の平方根を使用してそれが素数であるかどうかを判断するという私の論理を固めようとしており、それを他の人に説明しようとしています

問題は 5 行目で発生します。実装[False] * ((n-i*i-1)/(2*i)+1)が機能することはわかっていますが、その理由はわかりません。

n(エラトステネスのふるい)までの素数を見つける方法を書いています。はい、これは宿題です。私が書いた方法でパフォーマンスを改善しようとしています。ここ数日間、これを微調整してきましたが、与えられた疑似コードに従ってパフォーマンスを向上させることができません。

疑似コードは次のとおりです:
処理する数値のキューを作成
します 2 から n までの整数でキューを埋めます
素数を格納する空の結果キューを作成します
次の手順を繰り返します:
数値のキューから最初の値を削除して、次の素数 p を取得します
p を素数の結果キューに入れる p
で割り切れるすべての数を削除する数のキューをループします
(p は n の平方根より小さい)
残りの値はすべて素数であるため、素数の結果キューに転送します

これが私の現在の方法です：

64 ビット整数 (32 ビットより大きい) の約数を取得しようとしています。

私の最初の方法 (小さい数値の場合) は、結果の数値が 1 になるまで数値を除算し、一致する素数の数を数え、式 (1 + P1) (1+ P2) ..*(1 + Pn) = Numberを使用することでした。約数

例えば：

24 = 2 * 2 * 2 * 3 = 2^ 3 * 3^ 1

==> ( 3 + 1)*( 1 + 1) = 4 * 2 = 8 除数

しかし、大きな整数の場合、このメソッドは多くの反復を必要とします。2乗数を使って因数分解するQuadratic sieveという方法を見つけました。私のスクリプトを使用すると、数値がはるかに小さいため、これははるかに簡単になります。

私の質問は、この Quadratic Sieve をどのように実装できますか?

次のコードを使用して、単純なふるいを生成しました-

しかし、bまでの素数を見つけるために使用される余分な時間を排除したいので、m = (ab)/2を作成し、ゼロではなくb/2とsqrt b/2からメインのforループを開始しようとしましたが、そうではありませんどうすれば余分な計算を減らすことができますか? 前もって感謝します。