範囲内の素数を見つける最も速い方法は何ですか？

Question

私は素数を見つけるために、このコードを持っている：

void writePrimesToFile(int begin, int end, ofstream& file) 
{ 
bool isPrime = 0; 
for (int i = begin; i < end; i = i+2) 
{ 
    isPrime = 1; 
    for (int j = 2; j<i; j++) 
     if (i % j == 0) 
     { 
      isPrime = 0; 
      break; 
     } 
    if (isPrime) 
     file << i << " \n"; 
} 
} 

はそれを行うためのより高速な方法はありますか？ 私はグーグルでより速い方法を試みましたが、そのすべての数学と私はどのようにコードに変換することができないのか分かりません。

Answer 1

速い方法がありますか？

はい。迅速な素数性テストアルゴリズムがあります。

範囲の素数を見つけるため最速方法は何ですか？

誰も知らない。ある人が知っているならば、その人は非常に重要な秘密を守っています。既知の技術のいずれかが素数をテストする最速の方法であることを証明することはできませんでした。

---

あなたは求めているかもしれません：範囲内の素数を見つけるための最速の知ら方法は何ですか。

これに対する答えは次のとおりです。いくつかのアルゴリズムの複雑さは、他のアルゴリズムよりも漸進的に遅くなりますが、入力数値が小さい場合は無関係です。いくつかの数値では非常に高速ですが、確定的な方法よりも遅い問題のあるケースがあります。

あなたの入力番号はタイプがintであり、したがって非常に限られた範囲であるため、入力番号は小さいです。数字が小さいと、単純なアルゴリズムはより複雑なアルゴリズムより速くなる場合があります。あなたのユースケースに対してどのアルゴリズムが最速かを知るためには、それらをベンチマークする必要があります。

それはあなたのナイーブなアプローチよりも漸近的に高速であるため、私はSieve of Eratosthenesから始まるお勧めしますが、また、簡単には（ウィキペディアの擬似コードの礼儀）を実装するために：私はでき

Input: an integer n > 1 

Let A be an array of Boolean values, indexed by integers 2 to n, 
initially all set to true. 

for i = 2, 3, 4, ..., not exceeding √n: 
    if A[i] is true: 
    for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n : 
     A[j] := false 

Output: all i such that A[i] is true.