HDU - 4548 - 美素数【数论 + 打表】题解

柔光的暖阳◎ 2021-07-25 02:22 423阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明想考考你对素数的认识。  
问题是这样的：一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”，如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

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    const int maxn=1e6+10;
    int prime[maxn],b[maxn]={ 0},num=0,a[maxn];
    using namespace std;
    void find_prime() 素数打表 
    { 
    	b[1]=1;
    	for(int i=2;i<maxn;i++)
    	{ 
    		if(b[i]==0)
    		{ 
    			prime[num++]=i;
    			for(int j=i+i;j<maxn;j+=i)
    		    	b[j]=1;
    		}
    	}
    }
    int sum(int x) //求各位之和 
    { 
    	int sum=0,d;
    	while(x)
    	{ 
    		d=x%10;
    		sum=sum+d;
    		x/=10;
    	}
    	return sum;
    }
    void meiprime()///区间打表 
    { 
      int cnt=0;
      for(int i=1;i<=maxn;i++) { 
       if(b[i]==0&&b[sum(i)]==0)
         cnt++;
      a[i]=cnt;
      }
    }
    int main()
    { 
       find_prime();///不要忘记 
       meiprime(); 
       int n,left,right,flag=0;
       cin>>n;
       while(n--)
       { 
       	  cin>>left>>right;
          printf("Case #%d: %d\n",++flag,a[right]-a[left-1]);
       }
       return 0;
    }