用筛法求之N内的素数。
时间: 2024-02-25 09:54:39 浏览: 63
O(n)筛法求素数
5星 · 资源好评率100%
好的,这个问题可以使用筛法(埃氏筛法)求出N以内的素数,具体C++实现如下:
```c++
#include <iostream>
#include <cstring> // 用于memset函数
using namespace std;
const int MAXN = 100000; // 定义最大范围
bool isPrime[MAXN + 1]; // 定义布尔数组,用于判断素数
void sieve(int n) {
memset(isPrime, true, sizeof(isPrime)); // 初始化所有数为素数
for (int i = 2; i * i <= n; i++) { // 从2开始遍历到sqrt(n)
if (isPrime[i]) { // 如果i是素数
for (int j = i * i; j <= n; j += i) { // 将i的倍数全部标记为合数
isPrime[j] = false;
}
}
}
}
int main() {
int n; // 定义范围n
cout << "请输入范围n:";
cin >> n;
sieve(n); // 求出n以内的素数
cout << "范围[2, " << n << "]内的素数有:" << endl;
for (int i = 2; i <= n; i++) { // 输出范围内的素数
if (isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
我们先定义了一个常量MAXN,表示最大范围,以及一个布尔数组isPrime,用于判断素数。接着,我们定义了一个sieve函数,该函数使用筛法求出n以内的素数。具体实现如下:
1. 初始化所有数为素数,即将isPrime数组中的所有元素赋值为true;
2. 从2开始遍历到sqrt(n),如果当前数字i是素数,则将i的倍数全部标记为合数;
3. 遍历结束后,isPrime数组中为true的数字即为素数。
然后,我们在主函数中输入范围n,调用sieve函数求出n以内的素数。最后,使用cout输出结果。在输出时,我们需要添加文字说明,如:输出“范围[2, N]内的素数有:”,并且每个素数之间需要用空格隔开。
阅读全文