用c++编写程序用筛选法求100之内的素数
时间: 2023-12-03 21:27:29 浏览: 66
好的,下面是使用筛选法求100内素数的C++代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int main() {
const int N = 100;
bool is_prime[N + 1];
memset(is_prime, true, sizeof(is_prime)); // 初始化为全部是素数
for (int i = 2; i * i <= N; i++) { // 只需要枚举到根号N即可
if (is_prime[i]) { // 如果i是素数,则将i的倍数标记为合数
for (int j = i * i; j <= N; j += i) {
is_prime[j] = false;
}
}
}
cout << "100内的素数有:";
for (int i = 2; i <= N; i++) { // 输出所有素数
if (is_prime[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
在这个程序中,我们使用了一个布尔数组 `is_prime` 来记录每一个数是否是素数,初始时全部设置为素数。然后从2开始枚举,如果当前数是素数,则将其所有倍数标记为合数。最后,再次遍历数组,输出所有素数。
需要注意的是,我们只需要枚举到根号N即可,因为如果一个数不是素数,那么它必定可以表示成两个因子的乘积,其中一个因子必然小于等于根号N,另一个因子必然大于等于根号N。因此,我们只需要枚举到根号N即可。