c语言用筛选法求素数个数

在C语言中，我们可以使用筛选法（又称埃拉托斯特尼筛法，Sieve of Eratosthenes）来求解一定范围内素数的数量。这是一种古老而高效的算法，步骤如下：

1. 创建一个大小为n+1的布尔数组，初始全部设为true，表示0到n内的所有数字都是潜在的素数。
2. 从第一个质数2开始，将它的倍数标记为非素数（即数组中对应的值设为false）。因为除了2之外，所有的偶数都不是素数。
3. 继续查找下一个未被标记为非素数的数字，它是当前最大的素数的下一个整数。例如，如果找到的是3，就将其倍数也标记为非素数；然后找到5并继续这个过程，直到 sqrt(n)。
4. 最后，数组中仍然为true的位置就是素数。

以下是简单的C语言代码实现：

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

int countPrimes(int n) {
    bool primes[n + 1];
    memset(primes, true, sizeof(primes)); // 初始化为全部是素数
    primes[0] = primes[1] = false; // 0和1不是素数

    for (int i = 2; i * i <= n; i++) { // 只需检查到√n
        if (primes[i]) { // 如果i是素数
            for (int j = i * i; j <= n; j += i) { // 标记其倍数为非素数
                primes[j] = false;
            }
        }
    }

    int primeCount = 0;
    for (int i = 2; i <= n; i++) {
        if (primes[i]) {
            primeCount++;
        }
    }

    return primeCount;
}

int main() {
    int n;
    printf("请输入一个正整数: ");
    scanf("%d", &n);
    int result = countPrimes(n);
    printf("在%d到%d之间的素数有 %d 个.\n", 2, n, result);
    return 0;
}