c语言用欧拉筛输出1到n之间的质数

欧拉筛法是一种高效的筛选素数的方法，以下是使用C语言实现欧拉筛法输出1到n之间的所有质数的代码：

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

void euler_sieve(int n) {
    bool *is_prime = (bool*)malloc(sizeof(bool) * (n + 1)); // 申请动态内存
    int *prime = (int*)malloc(sizeof(int) * n);
    int cnt = 0; // 记录质数个数

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

    for (int i = 0; i < cnt; i++) {
        printf("%d ", prime[i]);
    }

    free(is_prime); // 释放动态内存
    free(prime);
}

int main() {
    int n;
    printf("请输入一个正整数 n：");
    scanf("%d", &n);
    printf("1 到 %d 之间的质数有：\n", n);
    euler_sieve(n);
    return 0;
}

代码解释：

1. 首先申请一个大小为 n+1 的布尔型数组 `is_prime`，用来标记是否为质数，初始值都为 false。
2. 申请一个大小为 n 的整型数组 `prime`，用来存储找到的质数。
3. 从 2 开始遍历到 n，如果当前数是质数，则将其加入 `prime` 数组，并更新质数个数 `cnt`。
4. 对于每个质数 p 和每个 i，如果 i*p <= n，则将 `is_prime[i*p]` 标记为 true，表示 i*p 不是质数。如果 i%p == 0，则退出内层循环，因为 i*p 的最小质因子已经是 p 了。
5. 最后遍历 `prime` 数组，输出所有质数。
6. 最后记得释放动态内存。

欧拉筛法时间复杂度为 O(nloglogn)，比普通的筛法 O(nlogn) 要快。