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);
}
}
上一篇:Gradle 1.12用户指南翻译


下一篇:超高性能的json序列化