c求小于等于n的所有素数的算法及实现

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用来找出小于或等于给定数n的所有素数的高效算法。其基本思想是从最小的素数2开始，找出所有2的倍数并排除掉，然后找到下一个没有被排除的数，它必然是一个素数，接着排除掉这个素数的所有倍数，如此重复，直到处理完小于或等于n的所有数。最终留下的数就是所有小于等于n的素数。

以下是使用埃拉托斯特尼筛法找出所有小于等于n的素数的C语言实现：

#include <stdio.h>
#include <string.h>

void sieveOfEratosthenes(int n) {
    int *prime = (int *)malloc((n + 1) * sizeof(int));
    memset(prime, 1, (n + 1) * sizeof(int));
    prime[0] = prime[1] = 0; // 0和1不是素数，所以设置为0

    for (int p = 2; p * p <= n; p++) {
        // 如果prime[p]没有被改变，那么它是一个素数
        if (prime[p] == 1) {
            // 更新所有p的倍数，设置为非素数（0）
            for (int i = p * p; i <= n; i += p) {
                prime[i] = 0;
            }
        }
    }

    // 打印所有小于等于n的素数
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    free(prime);
}

int main() {
    int n;
    printf("请输入一个正整数n：");
    scanf("%d", &n);
    printf("小于等于%d的所有素数是：\n", n);
    sieveOfEratosthenes(n);
    return 0;
}

这段代码首先创建了一个布尔数组`prime`来表示每个数是否为素数，然后使用埃拉托斯特尼筛法筛选出小于等于n的所有素数，并打印出来。