输出小于等于n的的质数的个数

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000

// 声明一个质数计数数组
int prime_count[MAX_N + 1];

// 埃拉托斯特尼筛法
void sieve_of_eratosthenes() {
    // 初始化质数数组，默认所有数都认为是质数
    int is_prime[MAX_N + 1];
    for (int i = 0; i <= MAX_N; i++) {
        is_prime[i] = 1;  // 假设所有数都是质数
    }
    is_prime[0] = is_prime[1] = 0;  // 0和1不是质数

    // 埃拉托斯特尼筛法
    for (int i = 2; i * i <= MAX_N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = 0;
            }
        }
    }

    // 计算每个数小于等于它的质数个数
    prime_count[0] = 0;
    for (int i = 1; i <= MAX_N; i++) {
        prime_count[i] = prime_count[i - 1] + is_prime[i];
    }
}

int main() {
    int T;
    scanf("%d", &T);  // 读取查询次数

    // 预处理所有质数信息
    sieve_of_eratosthenes();

    // 对于每个查询，输出小于等于n的质数个数
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", prime_count[n]);
    }

    return 0;
}

代码解析：

1. sieve_of_eratosthenes()：

   • 该函数使用埃拉托斯特尼筛法来标记质数。我们维护一个is_prime数组来标记每个数是否为质数。
   • 对于每个质数 p，标记 p^2, p^2 + p, p^2 + 2p,… 为非质数。
   • 然后，使用prime_count数组来记录每个数小于等于它的质数个数。

2. main()：

   • 首先读取查询次数T。
   • 然后对每个查询n，直接输出prime_count[n]，这表示小于等于n的质数个数。

时间复杂度：

• 埃拉托斯特尼筛法：时间复杂度为 O(nlog⁡log⁡n)，其中 n= 10^6。
• 查询阶段：每次查询的时间复杂度是 O(1)，因为我们直接查找预处理结果。

空间复杂度：

• 需要 O(n)的空间来存储is_prime和prime_count数组，最多需要 10^6 个元素。