请帮我用c++埃氏筛法写一个筛素数
时间: 2024-05-02 16:19:17 浏览: 98
好的,以下是用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++
埃拉托斯特尼筛法(Sieve of Eratosthenes),也称欧几里得筛法,是一种古老的用于寻找一定范围内所有质数的经典算法。在C++中,它通常通过动态数组实现。以下是简单的步骤:
1. 初始化一个大小为n+1的布尔型数组isPrime[],其中isPrime[i]表示i是否是质数。默认初始化为true,因为从2到n的所有数字都被认为可能是质数。
2. 遍历从2开始到√n(取整),对于每个质数p:
a. 如果isPrime[p]为true,说明p尚未被标记为合数,将它的倍数全部设为false。从p^2开始,每次加p,直到超过n为止。
3. 经过上述过程后,isPrime[]数组中的值为true的就是质数。因为除了2以外的偶数不是质数,所以我们可以直接跳过2,仅检查奇数。
以下是一个简单的C++实现示例:
```cpp
#include <iostream>
#include <vector>
std::vector<int> sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true);
isPrime[0] = false;
isPrime[1] = false;
for (int p = 2; p * p <= n; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
// 将索引转换为实际数值并返回质数列表
std::vector<int> primes;
for (int p = 2; p <= n; ++p)
if (isPrime[p])
primes.push_back(p);
return primes;
}
int main() {
int n;
std::cout << "Enter the number up to which you want to find prime numbers: ";
std::cin >> n;
std::vector<int> primes = sieveOfEratosthenes(n);
std::cout << "Prime numbers up to " << n << ": ";
for (const auto& prime : primes)
std::cout << prime << " ";
return 0;
}
```
阅读全文