请帮我用c++埃氏筛法写一个筛素数
时间: 2024-05-02 10:19:17 浏览: 122
好的,以下是用C语言实现埃氏筛法的代码,可以筛选出小于等于给定数值的所有素数:
```c
#include <stdio.h>
#define MAX_N 1000000
int is_prime[MAX_N + 1];
int main()
{
int n, count = 0;
scanf("%d", &n);
for (int i = 0; i <= n; i++)
is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
{
count++;
for (int j = i * 2; j <= n; j += i)
is_prime[j] = 0;
}
}
printf("小于等于%d的素数个数为%d\n", n, count);
return 0;
}
```
希望能帮到您,有什么其它问题可以直接问我哦。
相关问题
写一段C++埃氏筛法
以下是使用C语言实现的埃氏筛法:
```c
#include <stdio.h>
void sieveOfEratosthenes(int n) {
// 创建一个标志数组,用于标记是否为质数
int prime[n+1];
for (int i = 0; i <= n; i++) {
prime[i] = 1; // 初始化所有数字都假设为质数
}
// 将标志数组中的合数索引置为0
for (int p = 2; p * p <= n; p++) {
if (prime[p] == 1) {
// 将p的倍数标记为合数
for (int i = p * p; i <= n; i += p) {
prime[i] = 0;
}
}
}
// 输出所有的质数
printf("2 "); // 2是唯一的偶数质数,直接输出
for (int p = 3; p <= n; p += 2) {
if (prime[p] == 1) {
printf("%d ", p);
}
}
}
int main() {
int n;
printf("请输入一个正整数n:");
scanf("%d", &n);
printf("小于等于%d的所有质数为:\n", n);
sieveOfEratosthenes(n);
return 0;
}
```
c++用埃氏筛法求素数
### C++ 实现埃氏筛法求素数
以下是基于埃氏筛法原理编写的 C++ 示例代码,能够高效地找到指定范围内所有素数:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定义函数 sieveOfEratosthenes 来实现埃氏筛法
vector<int> sieveOfEratosthenes(int n) {
vector<bool> prime(n + 1, true); // 初始化布尔数组,默认全部为素数
prime[0] = prime[1] = false; // 0 和 1 非素数
for (int p = 2; p * p <= n; p++) { // 只需遍历至 sqrt(n)
if (prime[p]) { // 如果当前数是素数
for (int i = p * p; i <= n; i += p) { // 将其倍数标记为非素数
prime[i] = false;
}
}
}
vector<int> primes; // 存储最终的素数列表
for (int p = 2; p <= n; p++) {
if (prime[p]) primes.push_back(p);
}
return primes;
}
int main() {
int n;
cout << "Enter the upper limit to list all prime numbers: ";
cin >> n;
vector<int> primes = sieveOfEratosthenes(n);
cout << "Prime numbers up to " << n << ": ";
for (int prime : primes) {
cout << prime << " ";
}
cout << endl;
return 0;
}
```
上述代码实现了埃氏筛法的核心逻辑[^1]。通过创建一个布尔数组 `prime` 表示每个数的状态(是否为素数),并逐步将已知素数的倍数标记为非素数。
#### 关键点解析
- **初始化布尔数组**:初始假设所有大于等于 2 的数都是素数。
- **优化循环条件**:只需检查到 \( \sqrt{n} \),因为更大的因数必然有对应的小于 \( \sqrt{n} \) 的配对因子。
- **减少冗余计算**:从 \(p^2\) 开始标记倍数,而非从 \(2p\) 开始,进一步提升效率[^4]。
---
### 问题
阅读全文
相关推荐















