無限の首相を数える方法

Question

大したことないので、多分この質問をすっごく縮めてはいけませんでした...私はthe most efficient way to find the first 10000 primesの投稿を見ました。私はすべての可能な方法を探しています。目標は素数検査のためのワンストップショップを持つことです。人々が素数を見つけるために知っているすべてのテストは大歓迎です。

そしてそう：

• 素数を見つけるのすべてのさまざまな方法とは？

Answer 1

The Sieve of Eratosthenesまともなアルゴリズムです：

1. は、任意の天井に正の整数2のリストを取ります。
2. リスト内の次の項目（最初の反復では2）を取り出し、リストの最初から2番目の項目をすべて削除します。
3. 指定された天井に達するまで、手順2を繰り返します。
4. あなたのリストは純粋に素数で構成されています。

メモリの速度を交換するという点で機能的な制限があります。素数の非常に大きなリストを生成するときには、メモリ容量が必要でした。指定された整数の場合

Answer 2

、私が知っている最速の素数のチェックは次のとおりです。

1. 整数の平方根に2のリストを取ります。リストを
2. ループ、残りは、リスト内の任意の数のゼロである場合、整数が素数でない

   1. /整数現在の数をの残りの部分を取ります。
   2. リスト内のすべての数値の剰余が0でない場合、整数は素数です。

それはThe Sieve of Eratosthenesよりも大幅に少ないメモリを使用し、個々の数字のために、一般的に高速です。

Answer 3

2から整数のルートまでのリストを使用するアルゴリズムでは、2の後に奇数をテストするだけでパフォーマンスを向上させることができます。つまり、リストには2と3から正方形までの奇数が必要です整数の根。これにより、複雑さを増やさずにループを繰り返す回数が削減されます。

Answer 4

@theprise

私が代わりにインスタンス化リスト（膨大な数のためにメモリに問題が...）のインクリメントループを使用することを希望した場合、何がリストを作成せずにこれを行うには良い方法だろうか？

通常の数値（N％X）のチェックよりも、指定された整数（X％3）の除算チェックを行うほうが安いようには思えません。

Answer 5

素数を生成する方法を知りたい場合は、previous questionに記載されています。

Answer 6

@私にakdomの質問：

ルーピングは、私の以前の提案で正常に動作します、とあなたは数が偶数であるかどうかを判断するために、任意の計算を行う必要はありません。あなたのループ内で、以下に示すように、単純に、すべての偶数をスキップ：

//Assuming theInteger is the number to be tested for primality. 
// Check if theInteger is divisible by 2. If not, run this loop. 
// This loop skips all even numbers. 
for(int i = 3; i < sqrt(theInteger); i + 2) 
{ 
    if(theInteger % i == 0) 
    { 
     //getting here denotes that theInteger is not prime 
     // somehow indicate that some number, i, divides it and break 
     break; 
    } 
} 

Answer 7

をラトガースの大学院生は、最近recurrence relation that generates primesを見つけました。その連続する数字の違いは、素数または1を生成します。

これは、フィルタリングする必要があります。

b(1) = 1 
b(n) = b(n-1) + lcm(n,b(n-1)) 

次いで連続数の比、マイナス1 [B（N）/ B（N-1）-1]素数：ブノワクロワトルも同様の作業を行い、この再発を有しています。このすべての詳細は、Recursivityでお読みください。

ふるいの場合は、毎回ホイールを追加するのではなく、ホイールを使用して、Improved Incremental Prime Number Sievesをチェックしてください。ここには車輪の例があります。無視する2と5の数字を見てみましょう。彼らの車輪は、[2,4,2,2]です。

Answer 8

いくつかのプライムテストは、特定の数字でのみ動作します。たとえば、Lucas–Lehmerテストは、メルセンヌの数字に対してのみ機能します。

大きな数字に使用されるほとんどのプライムテストでは、特定の数字が「おそらく素数」であることがわかります（または、数字がテストに合格しなかった場合は、確かにではなくプライムです）。通常は、素数である可能性が非常に高くなるまでアルゴリズムを続行できます。

this pageをご覧ください。特に「参照」セクションをご覧ください。

Miller-Rabin testは、最高のテストの1つだと思います。 3.4 * 10^14の下の数字にテストを適用すると、各パラメータ2,3,5,7,11,13のテストに合格することが示されていますが、その標準形式では、 17、それはであり、確かにプライムです。

AKS testは、決定的で実績のある一般的な多項式時間検定であった。しかし、私の知る限りでは、入力が非常に大きい場合を除き、最良の実装は他のテストよりも遅くなることが判明しています。