用c++筛选法求一百以内的素数
时间: 2023-08-05 15:07:29 浏览: 49
以下是用C++实现的筛选法求一百以内的素数的代码:
```c++
#include <iostream>
using namespace std;
int main() {
bool isPrime[101];
// 初始化数组,所有数都先认为是素数
for(int i = 2; i <= 100; i++) {
isPrime[i] = true;
}
// 筛选法
for(int i = 2; i <= 50; i++) {
if(isPrime[i]) {
// 将i的倍数都标记为非素数
for(int j = i * 2; j <= 100; j += i) {
isPrime[j] = false;
}
}
}
// 输出结果
for(int i = 2; i <= 100; i++) {
if(isPrime[i]) {
cout << i << " ";
}
}
return 0;
}
```
在上面的代码中,我们使用了一个布尔类型的数组`isPrime`来记录每个数字是否为素数。首先将数组中的所有元素都初始化为`true`,然后从2开始循环到50,对于每个素数i,将它的倍数都标记为非素数,最后输出结果即可。
相关问题
C++用筛选法求100以内的素数
以下是用C++语言实现筛选法求100以内的素数的代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
const int maxn = 100;
bool prime[maxn + 1];
memset(prime, true, sizeof(prime)); // 初始化全部为true
for (int p = 2; p <= maxn; p++)
{
if (prime[p])
{
cout << p << " "; // 输出当前素数
for (int i = p * p; i <= maxn; i += p)
{
prime[i] = false; // 将当前素数的倍数标记为非素数
}
}
}
return 0;
}
```
程序首先定义了一个`prime`数组,表示当前下标对应的数是否为素数。然后使用`memset`函数初始化所有元素为`true`。
接着使用双重循环,外层循环从2开始枚举每个数,内层循环从当前素数的平方开始,每次增加素数个数的步长,将当前素数的倍数标记为非素数。
最后输出所有素数即可。
c++筛选法求100以内的素数的程序代码
以下是使用筛选法求100以内素数的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<bool> is_prime(101, true); // 初始化所有数字为素数
is_prime[0] = false; // 1 不是素数
for (int i = 2; i * i <= 100; ++i) {
if (is_prime[i]) { // 如果i是素数
for (int j = i * i; j <= 100; j += i) {
is_prime[j] = false; // 将i的倍数标记为合数
}
}
}
// 输出素数
cout << "100以内的素数有:";
for (int i = 2; i <= 100; ++i) {
if (is_prime[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
该程序中,使用 vector<bool> 存储每个数字是否为素数。初始化时,所有数字都被视为素数,然后从 2 开始,将其倍数标记为合数。最后输出所有素数即可。