G - 美素数

Bertha 。 2022-06-01 07:55 209阅读 0赞

##  ##

G - 美素数

HPU专题训练（-1）GCD&&素筛&&快速幂\_\_\_\_\_G - 美素数

小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明想考考你对素数的认识。  
　　问题是这样的：一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”，如29，本身是素数，而且2+9 = 11也是素数，所以它是美素数。  
　　给定一个区间，你能计算出这个区间内有多少个美素数吗？

Input第一行输入一个正整数T，表示总共有T组数据(T <= 10000)。  
接下来共T行，每行输入两个整数L，R(1<= L <= R <= 1000000)，表示区间的左值和右值。Output对于每组数据，先输出Case数，然后输出区间内美素数的个数（包括端点值L,R）。  
每组数据占一行，具体输出格式参见样例。Sample Input

3
    1 100
    2 2
    3 19

Sample Output

Case #1: 14
    Case #2: 1
    Case #3: 4

又做了一次：

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int maxn=1000000+6;
    bool p[maxn];
    int sum[maxn];
    
    bool prime(int n) //判断素数 
    {
    	if(n<2)	return 0;//小于2的不是素数 
    	int m=sqrt(n);
    	for(int i=2;i<=m;i++)
    		if(n%i==0)	return 0;//有其它约数的不是素数 
    	return 1;//上边两个排除之后，其他的就是素数了 
    }
    int main()
    {
    	memset(p,0,sizeof(p));
    	memset(sum,0,sizeof(p));
    	for(int i=1;i<=1000000;i++)
    	{
    		int j=i;
    		int z=0;//z是i的各位数之和 
    		while(j)
    		{
    			z+=j%10;
    			j/=10;
    		}
    		if(prime(z)&&prime(i))	p[i]=1;//	i是美素数的话，这个数记为1，否则为0 
    	}
    	for(int i=2;i<=1000000;i++)
    		sum[i]=sum[i-1]+p[i];//sum[i]记录的是从0->i 美素数的个数 
    	int t;
    	scanf("%d",&t);
    	for(int k=1;k<=t;k++)
    	{
    		int l,r;
    		scanf("%d %d",&l,&r);
    		printf("Case #%d: %d\n",k,sum[r]-sum[l-1]);
    	}
    	return 0;
    }

2018年1月24号写的代码，现在看起来真的不是很简洁：

/*
    思路：
    	先打表，把range内的美素数给找出来
    	用一个数组记录下来
    	然后统计[x,y]美素数的个数 
    	sum=d[y]-d[x-1] 
    	d[x]表示小于等于x的美素数的个数 
    */
    #include<stdio.h>
    #include<string.h>
    int b[1000000];
    int prime(int a)					//素数的判断 
    {
    	int z=1;
    	for(int i=2;i*i<=a;i++)
    	{
    		if(a%i==0)
    		{
    			z=0;
    			break;		
    		}		
    	}
    	return z;
    }
    void p()
    {
    	int m,n,j=0;
    	memset(b,0,sizeof(b));
    	for(int i=2;i<=1000000;i++)			//打表题目范围是小于等于一百万
    	{									//所以就开了这么大的范围
    		m=i;							//不能直接对i进行操作，不然会陷入死循环 
    		n=0;							//n是i的位数和 
    		while(m)						
    		{
    			n+=m%10;
    			m/=10;
    		}
    		if(prime(i)&&prime(n))			//判断i是不是美素数 
    		{
    		b[j]=i;
    		j++;
    		}
    	}
    	
    }
    int main()
    {
    	p();
    	int t;
    	scanf("%d",&t);
    	for(int i=1;i<=t;i++)
    	{
    		int l,r,j=0,s1=0,s2=0;
    		scanf("%d %d",&l,&r);
    		while(b[j]<l)					//判断小于l范围内有多少美素数 
    		{
    			s1++;
    			j++;	
    		}
    		j=0;	
    		while(b[j]<=r)					//判断小于等于r范围内有多少美素数 
    		{
    			s2++;
    			j++;	
    		}
    		printf("Case #%d: %d\n",i,s2-s1);	//ans=s2-s1; 
    	}
    	return 0;
    }