连续质数计算
时间: 2023-10-10 17:07:41 浏览: 102
连续质数是指在一段连续的整数范围内,存在一些质数,这些质数相邻之间差为1。例如:{2,3,5},{11,13},{17,19,23} 等都是连续质数。
计算一段连续整数范围内的连续质数,可以使用线性筛算法。具体实现步骤如下:
1. 定义一个数组is_prime[],用于判断一个数是否是质数。若is_prime[i]为true,则表示i是质数。
2. 定义一个数组prime[],用于存储已找到的质数。
3. 定义一个变量cnt,用于记录已找到的质数的个数。
4. 从2开始,依次枚举每个数i:
a. 若is_prime[i]为true,说明i是质数,将i加入prime数组中,cnt自增1。
b. 枚举prime数组中已找到的质数j,若j*i>n,则退出循环。
c. 若i能整除j,则说明i不是质数,将is_prime[i*j]赋值为false,并退出循环。
5. 最终,prime数组中的前cnt个元素即为所求的连续质数。
下面是一个C++的示例代码:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100000; // 线性筛范围
bool is_prime[MAXN + 5]; // 是否为质数
int prime[MAXN + 5]; // 存储质数
int cnt; // 质数个数
void linear_sieve(int n) {
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[cnt++] = i;
}
for (int j = 0; j < cnt && i * prime[j] <= n; ++j) {
is_prime[i * prime[j]] = false;
if (i % prime[j] == 0) {
break;
}
}
}
}
int main() {
int n;
cin >> n;
linear_sieve(n);
for (int i = 0; i < cnt; ++i) {
cout << prime[i] << " ";
}
cout << endl;
return 0;
}
```
输入一个整数n,输出不超过n的所有连续质数。时间复杂度为O(nloglogn)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)