题解 | 质数统计Java

import java.util.*;
import java.io.*;


public class Main {
    static int[] notPrime;
    static final int N = 1000000;

    static void ePrimes() {
        notPrime[0] = 1;
        notPrime[1] = 1;

        for (int n = 2; n * n <= N; ++n) {
            if (notPrime[n] == 1) continue;

            for (int j = n * n; j <= N; j += n) {
                notPrime[j] = 1;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                                              System.out)));

        notPrime = new int[1000001];
        ePrimes();
        int[] s = new int [1000001];
        for (int i = 1; i <= 1000000; ++i) {
            s[i] = s[i - 1] + (1 ^ notPrime[i]);
        }

        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; ++i) {
            int l, r;
            String[] input = new String[3];
            input = br.readLine().split(" ");
            l = Integer.parseInt(input[0]);
            r = Integer.parseInt(input[1]);

            out.println(s[r] - s[l - 1]);
        }
        out.flush();
    }
}