使用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;
}热门推荐
10 周岁宴舅舅祝福语简短
11 生日短袖祝福语简短英文
12 新年祝福语长辈简短红包
13 幼儿住院祝福语老师简短
14 创业大吉祝福语简短
15 老婆生日祝福语简短孩子
16 鼓励孩子小考祝福语简短
17 小寒健康祝福语大全简短
18 简短有内涵的祝福语