使用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;
}