用c++寫出埃拉托色尼筛法,要用using namespace std; 且要用bool另寫一個function
时间: 2024-02-18 15:05:17 浏览: 70
好的,以下是用C++编写的埃拉托色尼筛法,其中使用 `bool` 写了一个名为 `is_prime` 的函数:
```
#include <iostream>
#include <vector>
using namespace std;
bool is_prime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i*i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
vector<bool> sieveOfEratosthenes(int max) {
vector<bool> isPrime(max+1, true); // 初始化为true
isPrime[0] = isPrime[1] = false; // 0和1不是质数
for (int i = 2; i <= max; ++i) {
if (isPrime[i] && is_prime(i)) {
for (int j = i*i; j <= max; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
int main() {
int max = 100;
vector<bool> primes = sieveOfEratosthenes(max);
for (int i = 2; i <= max; ++i) {
if (primes[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
这个程序定义了一个 `is_prime` 函数,它接受一个整数 `n`,返回一个布尔值,表示 `n` 是否是质数。该函数的实现使用了常规的质数判断方法。程序还定义了一个 `sieveOfEratosthenes` 函数,实现了标准的埃拉托色尼筛法。它在筛选时调用了 `is_prime` 函数来确保只筛选质数的倍数。程序的 `main` 函数与之前相同,使用 `sieveOfEratosthenes` 函数来找出 0 到 100 中的所有质数,并将它们输出到屏幕上。
阅读全文