C语言编程代码质数筛（欧拉筛

以下是 C 语言实现欧拉筛的代码：

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

const int N = 1000010;

int prime[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    get_primes(n);
    for (int i = 0; i < cnt; i++) printf("%d ", prime[i]);
    return 0;
}

其中 `N` 表示筛选的范围，`prime` 数组存储筛出的质数，`st` 数组标记每个数是否为合数，`cnt` 表示质数的个数。在 `get_primes` 函数中，我们从小到大枚举每个数，如果该数是质数，则将其所有的倍数标记为合数，最终得到所有质数。

相关问题

编程实现计算欧拉函数值的算法C语言

#include <stdio.h>

int phi(int n) {
int result = n; // 初始化结果为 n
int i;
for (i = 2; i * i <= n; i++) {
if (n % i == 0) {
// i 是 n 的一个质因数
while (n % i == 0) {
// 除去所有 i 的因数
n /= i;
}
// 除去所有 i 的因数后，result 中要少了 i 的因数
result -= result / i;
}
}
if (n > 1) {
// n 是一个大于 sqrt(n) 的质数
result -= result / n;
}
return result;
}

int main() {
int n;
printf("请输入一个正整数 n：");
scanf("%d", &n);
printf("欧拉函数值为：%d\n", phi(n));
return 0;
}

c语言编程 输入一个0到1000000以内的数，判断0到该数间素数个数

我们可以用欧拉筛法来计算0到指定数之间素数的个数。首先，我们初始化一个布尔数组，其中的元素都为真，然后从2开始，将其倍数都设置为假，然后继续遍历到指定数，每次将其倍数设置为假，最终所有真值的元素就是素数。