请帮我用c++埃氏筛法写一个筛素数
时间: 2024-05-02 18:19:17 浏览: 11
好的,以下是用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
#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 存储找到的所有质数,最后输出了找到的质数的总数。
当然,如果你有更多问题,请继续问我!