/*
判断一个数是否是素数，只要判断这个数有没有在[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,0,
sizeof v);
memset(prime,0,
sizeof prime);
m=
0;
for(
int i=
2;i<maxn;i++
){
if(v[i]==
0){
v[i]=
i;
prime[++m]=
i;
}
for(
int j=
1;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,0,
sizeof flag);
for(
int i=
1;i<=m;i++
){
if(prime[i]*prime[i]>b)
break;
ll s=(a+prime[i]-
1)/prime[i];
//s是区间内第一个prime[i]的倍数
if(s<
2)s=
2;
//如果本身就是这个素数，即s==1,那么这个倍数就不用删掉就不用删掉
for(s=prime[i]*s;s<=b;s+=
prime[i])
flag[s-a]=
1;
}
ll ans=
0;
for(
int i=
0;i<=b-a;i++
)
ans+=
1-
flag[i];
return ans;
}
int main(){
int T;
init();
cin>>
T;
for(
int tt=
1;tt<=T;tt++
){
ll a,b;
cin>>a>>
b;
ll ans=
solve(a,b);
if(a==
1)ans--
;
printf("Case %d: %lld\n",tt,ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10428979.html
