C ++を使用して素数を見つけるための最速のアルゴリズムはどれですか？

エラトステネスのふるいは、nが約1,000万より小さい場合に、nより小さい素数を見つける最も効率的な方法の1つです。

エラトステネスのふるいを実演するプログラムは次のとおりです。

例

#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int num) {
   bool pno[num+1];
   memset(pno, true, sizeof(pno));
   for (int i = 2; i*i< = num; i++) {
      if (pno[i] == true) {
         for (int j = i*2; j< = num; j + = i)
         pno[j] = false;
      }
   }
   for (int i = 2; i< = num; i++)
   if (pno[i])
   cout << i << " ";
}
int main() {
   int num = 15;
   cout << "The prime numbers smaller or equal to "<< num <<" are: ";
   SieveOfEratosthenes(num);
   return 0;
}

出力

上記のプログラムの出力は次のとおりです。

The prime numbers smaller or equal to 15 are: 2 3 5 7 11 13

それでは、上記のプログラムを理解しましょう。

関数SieveOfEratosthenes（）は、引数として指定されたnumの前にあるすべての素数を検索します。このためのコードスニペットは次のとおりです。

void SieveOfEratosthenes(int num) {
   bool pno[num+1];
   memset(pno, true, sizeof(pno));
   for (int i = 2; i*i< = num; i++) {
      if (pno[i] == true) {
         for (int j = i*2; j< = num; j + = i)
         pno[j] = false;
      }
   }
   for (int i = 2; i< = num; i++)
   if (pno[i])
   cout << i << " ";
}

関数main（）は、numの値を設定してから、num以下のすべての素数を出力します。これは、関数SieveOfEratosthenes（）を呼び出すことによって行われます。このためのコードスニペットは次のとおりです。

int main() {
   int num = 15;
   cout << "The prime numbers smaller or equal to "<< num <<" are: ";
   SieveOfEratosthenes(num);
   return 0;
}