eratosthenes筛选法求素数c语言

埃拉托斯特尼筛法是一种古老的算法，用于寻找一定范围内所有质数。在C语言中，你可以通过创建一个数组来表示每个数字是否是质数，然后从2开始，逐步排除它的倍数。以下是简单的C代码实现：

#include <stdio.h>
#define MAX 100  // 可以根据需要调整最大值

void sieveOfEratosthenes(int primes[MAX]) {
    int i, j;
    for (i = 2; i * i <= MAX; i++) {  // 只需检查到√MAX，因为大于这个数的合数必有因子小于√MAX
        if (primes[i] == 0) continue;  // 如果i不是质数，则跳过
        for (j = i * i; j < MAX; j += i) {
            primes[j] = 0;  // 将i的倍数标记为非质数
        }
    }
}

int main() {
    int prime[MAX], count = 0;
    for (int i = 2; i < MAX; i++)
        prime[i] = 1;  // 初始化所有数为质数

    sieveOfEratosthenes(prime);  // 过滤出质数

    printf("Prime numbers up to %d are:\n", MAX);
    for (int i = 2; i < MAX; i++) {
        if (prime[i])
            printf("%d ", i), count++;  // 打印质数并计数
    }
    printf("\nTotal number of primes found: %d\n", count);

    return 0;
}

在这个程序中，`sieveOfEratosthenes`函数执行了筛法，而`main`函数展示了结果，并计算了质数的数量。