请写一个埃氏筛法的函数C++
时间: 2024-12-21 11:28:30 浏览: 39
当然可以。埃拉托斯特尼筛法(Sieve of Eratosthenes),也称为素数筛选法,是一种古老的用于找出一定范围内所有质数的经典算法。下面是一个简单的C++版本的埃氏筛法实现:
```cpp
#include <iostream>
#include <vector>
void sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true); // 创建一个布尔数组标记是否为素数
isPrime[0] = false; // 0和1不是素数
isPrime[1] = false;
for (int i = 2; i * i <= n; ++i) { // 只需要检查到√n
if (isPrime[i]) { // 如果i是素数
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false; // 将i的所有倍数标记为合数
}
}
}
// 输出所有素数
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
std::cout << i << " ";
}
}
}
int main() {
int limit;
std::cout << "请输入一个整数作为查找范围:";
std::cin >> limit;
sieveOfEratosthenes(limit);
return 0;
}
```
在这个程序中,我们首先初始化一个布尔数组`isPrime`,然后从2开始,将所有的质数倍数标记为非素数。最后遍历数组并打印出所有剩余未被标记为非素数的数字。
阅读全文
相关推荐

















