6k +/- 1ルールを使った試行分割素数テストの改良

Question

私は試行分割素数テストの基礎を踏襲し、それをコードで実装していました。時間のための）取引メモリは方形するふるいを作成することにより

2（N）のみ平方根まで試行除算を実行

1）：アルゴリズムの性能は、のような多くのトリックを使用して増大させることができます計算されたふるいの素数だけで試行分割を実行する

n%6（n mod 6）の値が見つかった場合は、結果をコンポジットとして返す考えはどこにもありませんでした。 1 or 5（6k +/- 1ルールを使用）。素数決定テストでこのルールを使用してもパフォーマンスは向上しませんか？はいの場合、なぜそれはどこに言及されていないのですか？いいえの場合、どうしてそうですか？

ありがとうございました。

Answer 1

あなたは初心者レベル（アイデアを思いついたことのない人）と極端なパフォーマンスを求める人の下のカテゴリに入るようです。だから、初心者に説明するのは少し難しく、非常に高度なものには簡単ではないようです。

実行時間を3分の1に短縮したり、同時に50％多くの数値をテストできるようにします。除数が大きすぎないというテストを少なくすることで、より多くの情報を保存できます。除数d = 6k-1のループがあり、dとd + 2 = 6k + 1をテストしたいとします。だから、あなたはd^2≤pだけをテストし、あなたは（d + 2）^ 2≤pをテストしないでください。最悪の場合、必要以上に1つの除数をテストします。最良の場合、（d + 2）^ 2≤pという数千のテストを保存します。

あなたが唯一の可能な素数が≥30であることを観察することによって、わずかに多くを保存することができ30K + 1、7、11、13、17、19、23、29、回避+ 5 30K及び30K + 25

Answer 2

n % 6のテストの考え方は、n % 2とn % 3のテストと完全に同じです。したがって、後者を通常の試験部門の一環として実行すると、前者を行うことは冗長です。が完済ん

A密接に関連したアイデアは（2を検討した後、3）にある@ gnasher729は、その優れた答えで説明としてのみ、フォーム6k+1、6k-1のトライアル約数を見てください。

Answer 3

このトリックの仕方：Mの製品を小さな素数の束にしてください。次に、数Nをテストするとき、（N％M）が0またはMと共通の要素を持つ場合、Nはコンポジットであるとすぐに言うことができます。

2と3の積6を使用しました。可能なモジュラス0,1,2,3,4,5、だけ1と5は2または3の係数を持っていません。

6については特別なことは何もありません - あなたは同じトリックを任意のモジュラスですが、複合モジュラスの密度を最大にするために小さな素数の積にする必要があります。 （gnasherが示すように）このチェックを行った後、あなたはここでしか一般的な方法がWheel Factorization呼ばれるM.

Answer 4

と共通の要素を持っていない裁判除数をテストする必要がある、ということ

注意。最も簡単なホイールは2つの特別なものを扱い、その後は奇数をテストすることです：2ホイール。次に簡単なのはあなたの質問で言及している2,3輪です。 @ gnasher729は、上記の2,3,5ホイールの数値を返します。

あなたは5

擬似コードから出発して、交互に2及び4を添加することにより、2,3-車輪の番号を生成することができる：これはふるいより少ないメモリを使用しているが、

boolean isPrime(num) 

    // Deal with factor 2. 
    if (num MOD 2 = 0) then 
    return (num = 2) 
    endif 

    // Deal with factor 3.  
    if (num MOD 3 = 0) then 
    return (num = 3) 
    endif 

    // Factors >= 5. 
    limit <-- 1 + sqrt(num) 
    trialFactor <-- 5 
    step <-- 2 
    while (trialFactor < limit) do 
    if (num MOD trialFactor = 0) 
     // Number not prime 
     return false 
    endif 
    trialFactor <-- trialFactor + step 
    step <-- 6 - step 
    endwhile 

    // Number is prime here. 
    return true 

end 

非常に大きな素数に対しては遅すぎる。