运行时间在1s内的时候，数量级要在107以内，108就会超时一般

呜呜呜，写的时候根本没有想到前缀和，之前的筛质数都是1-n,这里是[a,b]任意区间，应该是要想到的,对合数个数求一个前缀和，然后就可以在O(1)时间复杂度下求出任意区间的个数

数量级大的时候，开st[]数组用bool类型，以免MLE

//线性筛（筛质数）----------前缀和+筛质数
//直接求出1-N的全部合数个数，然后求出合数个数的前缀和，从而求出任意区间内的合数个数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e7+10;
int q[N];//存放筛出来的质数,用筛出来的质数去筛后面的合数
bool st[N];//记录有没有筛过，0-质数，1-合数
int s[N];//记录合数个数的前缀和
int cnt=0;
int a,b;
void prime(){
    for(int i=2;i<=N;i++){
       if(!st[i]) q[cnt++]=i;  
        for(int j=0;q[j]<=N/i;j++){
            if(!st[i*q[j]])st[i*q[j]]=true;
            if(i%q[j]==0)break;  //每个合数只会被自己的最小质因数筛掉
            }
    }
}
int main(){
    prime();
    for(int i=1;i<=N;i++)
    {
        if(st[i])s[i]=s[i-1]+1;
        else s[i]=s[i-1];
    } 
    while(cin>>a>>b)
    cout<<s[b]-s[a-1]<<endl;
    return 0;
}