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

柔光的暖阳◎ 2021-07-25 02:22 521阅读 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.代码

  1. #include<iostream>
  2. #include<cstdio>
  3. const int maxn=1e6+10;
  4. int prime[maxn],b[maxn]={ 0},num=0,a[maxn];
  5. using namespace std;
  6. void find_prime() 素数打表
  7. {
  8. b[1]=1;
  9. for(int i=2;i<maxn;i++)
  10. {
  11. if(b[i]==0)
  12. {
  13. prime[num++]=i;
  14. for(int j=i+i;j<maxn;j+=i)
  15. b[j]=1;
  16. }
  17. }
  18. }
  19. int sum(int x) //求各位之和
  20. {
  21. int sum=0,d;
  22. while(x)
  23. {
  24. d=x%10;
  25. sum=sum+d;
  26. x/=10;
  27. }
  28. return sum;
  29. }
  30. void meiprime()///区间打表
  31. {
  32. int cnt=0;
  33. for(int i=1;i<=maxn;i++) {
  34. if(b[i]==0&&b[sum(i)]==0)
  35. cnt++;
  36. a[i]=cnt;
  37. }
  38. }
  39. int main()
  40. {
  41. find_prime();///不要忘记
  42. meiprime();
  43. int n,left,right,flag=0;
  44. cin>>n;
  45. while(n--)
  46. {
  47. cin>>left>>right;
  48. printf("Case #%d: %d\n",++flag,a[right]-a[left-1]);
  49. }
  50. return 0;
  51. }

发表评论

表情:
评论列表 (有 0 条评论,521人围观)

还没有评论,来说两句吧...

相关阅读

    相关 素数

    我们经常会使用到素数打表这个工具,判断方法是多种多样的,下面我列举一种好理解的判断方法 思路: 1、初始化visit数组,初始化为true,用visit\[i\]=tr

    相关 HDU4548 素数

    问题链接:[HDU4548 美素数][HDU4548]。基础练习题,用C语言编写程序。 问题简述:参见上述链接。 问题分析:美素数定义为一个数是素数并且其各位数