首页 > 其他 > 详细

1407251735-hd-美素数.cpp

时间:2014-07-26 02:16:16      阅读:353      评论:0      收藏:0      [点我收藏+]
#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;
}

1407251735-hd-美素数.cpp,布布扣,bubuko.com

1407251735-hd-美素数.cpp

原文:http://blog.csdn.net/wangluoershixiong/article/details/38125785

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!