筛选法求100以内的素数c++
时间: 2023-12-06 08:35:50 浏览: 50
以下是使用筛选法求100以内素数的C++代码:
```c++
#include <iostream>
using namespace std;
int main() {
int arr[101] = {0}; // 容量为101的数组并将其全部赋值为0
for (int i = 2; i < 101; i++) {
if (arr[i] == 0) { // 如果当前数是素数
for (int j = i * 2; j < 101; j += i) {
arr[j] = 1; // 将其倍数全部标记为非素数
}
}
}
for (int i = 2; i < 101; i++) {
if (arr[i] == 0) { // 输出所有素数
cout << i << "是素数" << endl;
}
}
return 0;
}
```
相关问题
筛选法求100以内素数
以下是使用筛选法求100以内素数的Python代码:
```python
# 初始化一个100个元素的列表,全部赋值为1
is_prime = [1] * 100
# 1不是素数,将is_prime[0]赋值为0
is_prime[0] = 0
# 筛选法,从2开始到sqrt(100)结束
for i in range(2, int(100 ** 0.5) + 1):
# 如果i是素数
if is_prime[i - 1] == 1:
# 将i的倍数全部标记为合数,从i*i开始标记
for j in range(i * i, 100 + 1, i):
is_prime[j - 1] = 0
# 输出所有素数
for i in range(1, 100 + 1):
if is_prime[i - 1] == 1:
print(i, end=' ')
```
输出结果为:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
c++用筛选法求100以内的素数。
以下是使用筛选法求100以内素数的C++代码:
```c++
#include <iostream>
using namespace std;
int main() {
const int n = 100;
bool isPrime[n+1]; // 数组记录是否为素数
for(int i=2; i<=n; i++) {
isPrime[i] = true; // 先默认所有数都是素数
}
for(int i=2; i*i<=n; i++) {
if(isPrime[i]) {
// 如果当前数是素数,则将其倍数标记为非素数
for(int j=i*i; j<=n; j+=i) {
isPrime[j] = false;
}
}
}
// 输出所有素数
cout << "100以内的素数:";
for(int i=2; i<=n; i++) {
if(isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
在这个程序中,我们首先创建了一个长度为101的bool类型数组`isPrime`,用于记录每个数是否为素数。初始化时,我们将所有数都默认为素数。然后,我们从2开始遍历到$\sqrt{n}$,如果当前数是素数,则将其倍数都标记为非素数。最后,输出所有素数即可。