lightoj1197 素数双筛，可以参考poj的那题双筛

/*

判断一个数是否是素数，只要判断这个数有没有在[2,sqrt(n)]区间的因子

同样，对于大数短区间的筛选，同样可以用这种判断方式，

先筛出sqrt(n)范围内的素数，然后用这些素数去筛出区间内的因子

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000000

#define ll long long

int v[maxn],prime[maxn],m;

void init(){

    memset(v,,sizeof v);

    memset(prime,,sizeof prime);

    m=;

    for(int i=;i<maxn;i++){

        if(v[i]==){

            v[i]=i;

            prime[++m]=i;

        }

        for(int j=;j<=m;j++){

            if(prime[j]>v[i] || prime[j]*i>maxn)break;

            v[i*prime[j]]=prime[j];

        }

    }

}

int flag[maxn];

ll solve(ll a,ll b){

    memset(flag,,sizeof flag);

    for(int i=;i<=m;i++){

        if(prime[i]*prime[i]>b)break;

        ll s=(a+prime[i]-)/prime[i];//s是区间内第一个prime[i]的倍数

        if(s<)s=;//如果本身就是这个素数，即s==1,那么这个倍数就不用删掉就不用删掉

        for(s=prime[i]*s;s<=b;s+=prime[i])

            flag[s-a]=;

    }

    ll ans=;

    for(int i=;i<=b-a;i++)

        ans+=-flag[i];

    return ans;

}

int main(){

    int T;

    init();

    cin>>T;

    for(int tt=;tt<=T;tt++){

        ll a,b;

        cin>>a>>b;

        ll ans=solve(a,b);

        if(a==)ans--;

        printf("Case %d: %lld\n",tt,ans);

    }

}