P1865 A % B Problem（欧拉筛，永远的神）

#include<iostream>
#define N 1000001
using namespace std;
int  m,n,l,r ,b[N],ans[N];int a[N]={1,1};
int tot=0;
int main()
{
  cin>>n>>m;int k;
  for(int i=2;i<=m;i++)//这个意思是在m里面找到质数并且标记 ，质数最小是2，所以i=2 
  {
    ans[i]=ans[i-1];
    if (a[i]==0)//如果没有被标记为1，就是质数。 
      b[++k]=i;
      ans[i]=k; 
    for(int j=1;j<=k;j++)// //j小于当前所有的质数的个数
    {
      if(i*b[j]>m)break;// 如果超出给出的范围，那么就退出循环 
      a[i*b[j]]=1;//用质数数依次×i，结果标记为合数（也就是标记为1）。 
      if(i%b[j]==0)break;//最关键的只标记一次 
    } 
  }
  for(int i=1;i<=n;++i)
  {
    cin>>l>>r;
    if(l<1||r>m) cout<<"Crossing the line";
    else cout<<ans[r]-ans[l-1];
    cout<<endl;
  }
}