如何在ACM编程竞赛中利用C++实现埃氏筛法筛选素数?请提供C++代码实现。
时间: 2024-11-16 18:22:36 浏览: 16
埃氏筛法是一种高效筛选素数的方法,通过逐个排除非素数,留下素数。在ACM编程竞赛中,对算法的效率有极高的要求,因此掌握高效的素数筛选技巧是非常必要的。以下是一个C++代码示例,展示如何实现埃氏筛法:
参考资源链接:[ACM竞赛实用模板集粹](https://wenku.csdn.net/doc/3sdb3j1dq0?spm=1055.2569.3001.10343)
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = ***; // 定义最大范围
vector<int> primes; // 存储素数的数组
bool isNotPrime[MAXN + 1]; // 标记非素数
void sieve(int n) {
for (int i = 2; i <= n; ++i) {
isNotPrime[i] = false;
}
for (int i = 2; i * i <= n; ++i) {
if (!isNotPrime[i]) {
primes.push_back(i); // 素数入数组
for (int j = i * i; j <= n; j += i) {
isNotPrime[j] = true; // 非素数标记
}
}
}
}
int main() {
int n;
cin >> n;
sieve(n);
// 输出素数列表
for (int prime : primes) {
cout << prime <<
参考资源链接:[ACM竞赛实用模板集粹](https://wenku.csdn.net/doc/3sdb3j1dq0?spm=1055.2569.3001.10343)
阅读全文