首页 > 代码库 > 洛谷P2667 超级质数 [2017年6月计划 数论05]
洛谷P2667 超级质数 [2017年6月计划 数论05]
P2667 超级质数
题目背景
背景就是描述，描述就是背景。。。。。。
题目描述
一个质数如果从个位开始，依次去掉一位数字，两位数字，三位数字。。。。。。直到只剩一位数字中间所有剩下的数都是质数，则称该质数为一个超级质数。例如：2333是一个质数，因为2333,233,23,2都是质数，所以2333是一个四位超级素数。请你写一个程序，给定一个整数X，求大小小于X的超级质数。
输入输出格式
输入格式：一行，给出一个整数X(1<=X<=100000000).
输出格式：第一行，一个整数k，表示X以内超级质数的个数.
第2至k+1行，每行一个整数，输出所有X以内的超级质数，这些数按从小到大的顺序排列。
输入输出样例
输入样例#1：
100
输出样例#1：
132357232931375359717379
说明
对于30%的数据，X<=1000。
对于100%的数据，X<=100000000。
最后一道数学水题了。
1 #include <bits/stdc++.h> 2 const int INF = 0x3f3f3f3f; 3 inline void read(long long &x) 4 { 5 x = 0;char ch = getchar();char c = ch; 6 while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar(); 7 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar(); 8 if(c == ‘-‘)x = -x; 9 }10 11 long long x;12 13 long long a;14 15 bool IsPrime(long long k)16 {17 long long a = sqrt(k);18 for(int i = 2;i <= a;i ++)19 {20 if(k % i == 0)21 {22 return false;23 }24 }25 return true;26 }27 28 long long prime[1000];29 30 long long num[10];31 int head,tail;32 int main()33 {34 read(x);35 if(x < 2){printf("0");return 0;}36 if(x < 3){printf("1\n2");return 0;}37 if(x < 5){printf("2\n2\n3");return 0;}38 if(x < 7){printf("3\n2\n3\n5");return 0;}39 if(x < 23){printf("4\n2\n3\n5\n7");return 0;}40 head = 1;41 tail = 4;42 prime[1] = 2;43 prime[2] = 3;44 prime[3] = 5;45 prime[4] = 7;46 num[0] = 1;47 num[1] = 3;48 num[2] = 7;49 num[3] = 9;50 while(head <= tail)51 {52 for(int i = 0;i <= 3;i ++)53 {54 long long tmp = prime[head] * 10 + num[i];55 if(tmp <= x && IsPrime(tmp))56 {57 prime[++tail] = tmp;58 }59 if(tmp > x)goto L1;60 }61 head ++;62 }63 L1:64 printf("%d\n", tail);65 for(int i = 1;i <= tail;i ++)66 {67 printf("%d\n", prime[i]);68 }69 return 0;70 }
洛谷P2667 超级质数 [2017年6月计划 数论05]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。