筛法求素数的c语言函数怎么写

筛法是一种常用的求解一定范围内素数的高效算法，如埃拉托斯特尼筛法（Sieve of Eratosthenes）。在C语言中，可以按照以下步骤编写一个简单的埃拉托斯特尼筛法函数：

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

void sieve_of_eratosthenes(int n, bool prime[]) {
    // 初始化布尔数组，所有元素初值设为true
    for (int i = 2; i * i <= n; i++) {
        // 如果prime[i]还是true，说明i是素数
        if (prime[i]) {
            // 将i的倍数标记为非素数
            for (int j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }

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

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

    // 创建足够大的布尔数组存储素数状态
    bool* primes = (bool*)malloc(sizeof(bool) * (limit + 1));
    for (int i = 0; i <= limit; i++) {
        primes[i] = true;
    }

    sieve_of_eratosthenes(limit, primes);
    free(primes);
    return 0;
}

在这个函数中，我们创建了一个布尔数组`prime[]`，并从2开始遍历到√n，将每个素数的倍数都标记为非素数。最后，打印出所有未被标记的数，它们就是素数。