用C++语言写一个欧拉筛

欧拉筛是一种用于求质数的算法，它的基本思想是先将所有的数都标记为质数，然后从小到大遍历每个质数，将其所有的倍数标记为合数，直到遍历完所有的质数。最后，没有被标记为合数的数就是质数。

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

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

int main() {
    int n;
    printf("请输入一个整数n：");
    scanf("%d", &n);

    // 标记数组，0表示质数，1表示合数
    int *is_prime = (int*)malloc(sizeof(int) * (n + 1));
    for (int i = 2; i <= n; i++) {
        is_prime[i] = 0; // 初始化为质数
    }

    // 求质数
    for (int i = 2; i <= n; i++) {
        if (is_prime[i] == 0) { // 如果是质数
            printf("%d ", i); // 输出质数
            for (int j = i * i; j <= n; j += i) { // 将其倍数标记为合数
                is_prime[j] = 1;
            }
        }
    }

    free(is_prime); // 释放内存
    return 0;
}

在上述代码中，我们使用了动态内存分配来创建标记数组is_prime。在求质数时，从2开始遍历每个数，如果它是质数，则输出它，并将它的所有倍数（不包括它本身）标记为合数。最后，输出所有的质数。