HPUOJ---2017寒假作业--专题-1/G-美素数

G - 美素数

31 1002 23 19Sample Output
Case #1: 14Case #2: 1Case #3: 4
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define max 1000000+11 int QUICK(int y){	int p,sum=0,i,j;	while(y)	{		p=y%10;		sum+=p;		y/=10;	}	return sum;}int a[max],b[max],c[max];int main(){	int i,j,sum,count=0,p;	memset(a,0,sizeof(a));	memset(b,0,sizeof(b));	memset(c,0,sizeof(c));            //数组清零 	a[0]=a[1]=1;	for(i=2;i*i<=max;i++)	{		if(!a[i])		{			for(j=i*i;j<max;j+=i)			{				a[j]=1;//下标是否为素数，通过对应数据为0，或1，来体现出来。 			}		}	}	for(i=2;i<=max;i++)	{		if(!a[i])//判断i是否为素数 ，在此基础上，判断sum 		{			p=i;			sum=QUICK(p);//i的各位数字之和，该和也在0到max之间，第一次循环数组a已判断出 			if(!a[sum])//判断和sum是否素数 			{				b[i]=1; //两个条件同时成立，则为美素数，数组b来存 			}   		}	}	for(i=1;i<=max;i++)	{		if(b[i])//判断是否是美素数 		   count++;//一直在加，得到的是从1开始到i的所有美素数的个数 		c[i]=count;//i也一直变化，每一个下标对应的都是到此所有美素数个数 	}	int T,L,R,n,k=1; 	scanf("%d",&T); 	while(T--) 	{ 		scanf("%d%d",&L,&R); 		PRintf("Case #%d: %-d/n",k++,c[R]-c[L-1]);//L到R的所有美素数     }    return 0;}