首页 > 代码库 > 1407251735-hd-美素数.cpp
1407251735-hd-美素数.cpp
#include<stdio.h>
int s1[1005000],s2[1005000];
//若在main函数外面定义数组，则数组为全局变量，数组自动初始化为0；
//而在main函数里面定义数组的话千万记得要初始化
int main()
{
int n,l,r;
int a,b,c,d,g=1;
//素数打表法
s1[0]=s1[1]=1;
for(a=0;a<1000000;a++)
{
if(s1[a])
continue;
for(b=a+a;b<1000000;b+=a)
s1[b]++;
}
d=0;
for(a=0;a<1000000;a++)
{
b=a;
c=0;
while(b)
{
c+=b%10;
b/=10;
}
if(s1[c]==0&&s1[a]==0)
d++;//d是美素数的个数
s2[a]=d;//s2【a】存的是从 0到 a之间美素数的个数
}
scanf("%d",&n);
//将数据写到外面，每次使用直接调用就好，这些数据只计算了一次，所以省下了时间
while(n--)
{
scanf("%d%d",&l,&r);
printf("Case #%d: ",g);
g++;
printf("%d\n",s2[r]-s2[l-1]);
}
return 0;
}
int s1[1005000],s2[1005000];
//若在main函数外面定义数组，则数组为全局变量，数组自动初始化为0；
//而在main函数里面定义数组的话千万记得要初始化
int main()
{
int n,l,r;
int a,b,c,d,g=1;
//素数打表法
s1[0]=s1[1]=1;
for(a=0;a<1000000;a++)
{
if(s1[a])
continue;
for(b=a+a;b<1000000;b+=a)
s1[b]++;
}
d=0;
for(a=0;a<1000000;a++)
{
b=a;
c=0;
while(b)
{
c+=b%10;
b/=10;
}
if(s1[c]==0&&s1[a]==0)
d++;//d是美素数的个数
s2[a]=d;//s2【a】存的是从 0到 a之间美素数的个数
}
scanf("%d",&n);
//将数据写到外面，每次使用直接调用就好，这些数据只计算了一次，所以省下了时间
while(n--)
{
scanf("%d%d",&l,&r);
printf("Case #%d: ",g);
g++;
printf("%d\n",s2[r]-s2[l-1]);
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。