程序说明

线性筛+判断输入区间。注意题目要求是输出个数，第一次提交有一部分数据RE了。。结果发现是数组开成了1000000，除此之外把原本是int类型的isprime数组换成了boolean之后通过了。

代码如下：

import java.util.*;
import java.io.*;
public class Main {
    static boolean isprime[] = new boolean[1000001];
    static int prime[] = new int[1000001];
    public static void main(String[] args) {
        int n, m, l, r;
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        n = sc.nextInt();
        m = sc.nextInt();   
        fun(m);
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            l = sc.nextInt();
            r = sc.nextInt();
            if(l < 1 || r > m) {
                System.out.println("Crossing the line");
                continue;   
            }
            else {
                for(int j = l; j <= r; j++)
                    if(isprime[j])
                        cnt++;                  
                System.out.println(cnt);                
            }           
        }
    }   
    static public void fun(int n) { 
        int i, j;
        int cnt = 0;
        for(i = 0; i <= n; i++)
            isprime[i] = true;
        isprime[0] = false;
        isprime[1] = false;
        for(i = 2; i <= n; i++) {
            if(isprime[i]) 
                prime[cnt++] = i;
            for(j = 0; i * prime[j] <= n && j < cnt; j++) {
                isprime[i * prime[j]] = false;
                if(i % prime[j] == 0) 
                    break;
            }
        }
    }
}