统计n以内有素数个数C语言

在C语言中统计小于等于给定整数n内的素数个数，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这个算法的基本思想是从2开始，逐步将每个素数的倍数标记为合数，直到遍历到n为止。以下是简单的实现步骤：

1. 定义一个数组isPrime，大小为n+1，初始化所有元素为true，表示从0到n的所有数字都是潜在的素数。
2. 从第一个未被标记的数2开始，依次检查它的倍数，如果倍数未被标记，则它是一个素数，并增加计数器。同时，将这些倍数标记为合数。
3. 遍历到sqrt(n)，因为之后的数不可能再成为更大的数的素因数。
4. 最终计数器的值就是小于等于n的素数个数。

以下是简化的C代码实现示例：

#include <stdio.h>
#include <math.h>

int countPrimes(int n) {
    int limit = sqrt(n);
    int isPrime[n + 1], count = 0;
    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i]) {
            count++;
            // 标记所有该素数的倍数为合数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = 0;
            }
        }
    }
    // 因为最后一个被检查过的数可能是素数，所以最后加上1
    count += isPrime[limit] ? 1 : 0;
    return count;
}

int main() {
    int n;
    printf("请输入一个整数n: ");
    scanf("%d", &n);
    int primeCount = countPrimes(n);
    printf("小于等于%d的素数个数是：%d\n", n, primeCount);