首先数据范围太大，一开始我想的是，用欧拉筛处理出1~sqrt(1<<31-1)内的素数，然后枚举[a,b]内的所有数，用预处理的素数进行判断。但一直t。
正解：
根据b-a<=1e5，所以可以对a和b的不同取值进行分类。
先用欧拉筛处理出1e5以内的所有的素数，用vis1数组标记。
当a<=1e5&&b<=1e5时：直接枚举计数即可。
此外，用另一个数组标记，但由于数值较大，不能开那么大的数组，所以就可以把所有的数-a，使得所有的数据变小。
然后利用之前处理的素数，来判断区间[a,b]的数是否为素数（埃氏筛的思想），标记。然后遍历计数。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
bool vis1[N],vis2[N];
int prime[80000],cnt;
typedef long long ll;
void euler()
{
    memset(vis1,0,sizeof(vis1));
    cnt=0;
    vis1[1]=1;
    for(int i=2;i<=N-5;i++)
    {
        if(!vis1[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N-5;j++)
        {
            vis1[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
    int t,cas=0;
    euler();//cout<<cnt<<endl;
    scanf("%d",&t);
    ll a,b;
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        int ans=0;
        if(a<=N-5&&b<=N-5)
        {
            for(ll i=a;i<=b;i++)
                if(!vis1[i])
                    ans++;
        }
        else
        {
            memset(vis2,0,sizeof(vis2));
            for(int i=1;i<=cnt&&prime[i]*prime[i]<=b;i++)
            {
                for(ll j=a/prime[i]*prime[i];j<=b;j+=prime[i])
                {
                    if(j>=a&&!vis2[j-a])
                        vis2[j-a]=1;
                }
            }
            for(int i=0;i<=b-a;i++)
                if(!vis2[i])
                    ans++;
        }
        printf("Case %d: %d\n",++cas,ans);
    }
    return 0;
}