import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0; i < T; i++){
            int a = sc.nextInt();
            int count = 0;
            for(int j = 1; j <= a; j++){
                if(prime(j)){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
     public static boolean prime(int a){
        if(a <= 1){
            return false;
        }else if(a == 2){
            return true;
        }else if(a % 2 == 0){
            return false;
        }else{
            for(int i = 3; i * i <= a; i++){
                if(a % i == 0){
                    return false;
                }
            }
            return true;
        }
    }
}
一开始写的代码，运行时间太长，不通过。 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int maxN = 1000000;
        int[] primeCount = sieve(maxN);
        
        // 处理每个查询
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            System.out.println(primeCount[n]);
        }
    }
    
    // 使用埃拉托斯特尼筛法预处理质数个数
    public static int[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        int[] primeCount = new int[n + 1];
        
        // 初始化：假设所有数都是质数
        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;
                }
            }
        }
        
        // 计算前缀和：小于等于i的质数个数
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                count++;
            }
            primeCount[i] = count;
        }
        
        return primeCount;
    }
}

埃拉托斯特尼筛法在 n=10 时的详细步骤

当 n=10 时，埃拉托斯特尼筛法的执行过程如下：

1. 初始化阶段

  • 创建数组 isPrime[0...10]，默认值为 false。
  • 显式将 isPrime[2...10] 设为 true，表示初始假设这些数是质数。
    plaintext 
    索引: 0  1  2  3  4  5  6  7  8  9  10
值:   F  F  T  T  T  T  T  T  T  T  T

2. 筛选阶段（外层循环 i 从 2 到 3）

  • i = 2（质数）：
    • 标记 2 的倍数（从 2²=4 开始）：4, 6, 8, 10 为 false。
    plaintext 
    索引: 0  1  2  3  4  5  6  7  8  9  10
值:   F  F  T  T  F  T  F  T  F  T  F

  • i = 3（质数）：
    • 标记 3 的倍数（从 3²=9 开始）：9 为 false。
    plaintext 
    索引: 0  1  2  3  4  5  6  7  8  9  10
值:   F  F  T  T  F  T  F  T  F  F  F

  • i = 4：
    • isPrime[4] = false，跳过。
  • i = 5：
    • i²=25 > 10，外层循环终止。

3. 前缀和计算阶段

  • 遍历 isPrime 数组，计算前缀和 primeCount：
    java 
    int count = 0; for (int i = 1; i <= 10; i++) { if (isPrime[i]) count++; primeCount[i] = count; }


    plaintext 
    索引: 0  1  2  3  4  5  6  7  8  9  10
isPrime: F  F  T  T  F  T  F  T  F  F  F
count:   0  0  1  2  2  3  3  4  4  4  4


4. 查询结果

  • 查询 n=10：
    • 直接返回 primeCount[10] = 4（质数为 2, 3, 5, 7）。