求1～n的素数个数c语言

以下是求1~n的素数个数的C语言代码：

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

int countPrimes(int n) {
    bool isPrime[n + 1];
    int count = 0;

    // 初始化标记数组
    for (int i = 2; i <= n; i++) {
        isPrime[i] = true;
    }

    // 筛选素数
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 统计素数个数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }

    return count;
}

int main() {
    int n = 100;  // 求1~100的素数个数
    int count = countPrimes(n);
    printf("1~%d中共有%d个素数\n", n, count);
    return 0;
}

该算法采用埃氏筛法来筛选素数，时间复杂度为 O(nloglogn)。