使用C ++查找质数最快的算法是哪一种？

Eratosthenes筛是在n小于1000万左右时找到小于n的素数的最有效方法之一。

给出了演示Eratosthenes筛的程序，如下所示。

示例

#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;
}