请帮我用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语言实现的埃氏筛法：

#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++实现示例：

#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;
}