数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 查找质数的最快速算法是什么？
埃拉托色尼筛法是最有效的方法之一，用于找出小于 n 的质数，其中 n 小于 1000 万左右。
如下所示，展示了埃拉托色尼筛法的程序。
示例
#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;
}
更新于:2020 年 6 月 26 日
3K+ 浏览次数
广告