请帮我用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++代码实现埃氏筛法

当然，我能够帮你回答这个问题！以下是 C 代码实现埃氏筛法的示例:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXN 10000000

bool is_prime[MAXN + 5]; // 用于判断是否为质数的布尔数组
int prime[MAXN + 5]; // 存储筛出的所有质数
int tot_prime; // 质数的总数

void sieve(int n) {
  for (int i = 2; i <= n; i++) {
    if (is_prime[i] == false) { // 如果 i 是质数，则将其标记为 true
      tot_prime++;
      prime[tot_prime] = i;
    }
    for (int j = 1; j <= tot_prime && prime[j] * i <= n; j++) { // 卡成 <= n 不多余计算
      is_prime[i * prime[j]] = true; // i * prime[j] 不是质数
      if (i % prime[j] == 0) { // 卡成最小询问，坑点
        break;
      }
    }
  }
}

int main() {
  sieve(1000000);
  printf("%d\n", tot_prime);
  return 0;
}

上述代码实现了介绍的埃氏筛法，用布尔数组 is_prime 存储每个数是否为质数，用数组 prime 存储找到的所有质数，最后输出了找到的质数的总数。

当然，如果你有更多问题，请继续问我！