题目描述
样例
const int M=1e6+5,N=(1<<16);
int prime[N+5],is[N+5],tot;
void getprime()
{
is[1]=1;//mmpaaaaaaaaaaaaaaaa
for(int i=2;i<=N;++i)
{
if(!is[i]) prime[++tot]=i;
for(int j=1;j<=tot&&(ll)i*prime[j]<=N;++j)
{
is[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int issp[M];
int main()
{
getprime();
int T,cas=0;scanf("%d",&T);
while(T--)
{
m(issp,0);
int a,b;scanf("%d%d",&a,&b);
if(a<=N&&b<=N)
{
int ans=0;
for(int i=a;i<=b;++i)
if(!is[i]) ++ans;
printf("Case %d: %d\n",++cas,ans);
continue;
}
int ans=0;
if(a<=N)
{
for(int i=a;i<=N;++i)
if(!is[i]) ++ans;
a=N+1;
}
for(int i=1;i<=tot;++i)
{
ll l=a/prime[i]*prime[i];//左端点l.
if(l<a) l+=prime[i];
if(l==prime[i]) l+=prime[i];
for(ll j=l;j<=b;j+=prime[i]) issp[j-a]=1;
}
for(int j=a;j<=b;++j)
if(!issp[j-a]) ++ans;
printf("Case %d: %d\n",++cas,ans);
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla