首页 > 代码库 > poj3247:回文素数
poj3247:回文素数
总时间限制: 5000ms 内存限制: 65536kB描述一个数如果从左往右读和从右往左读数字是相同的,则称这个数是回文数,如121,1221,15651都是回文数。给定位数n,找出所有既是回文数又是素数的n位十进制数。(注:不考虑超过整型数范围的情况)。输入位数n,其中1<=n<=9。输出第一行输出满足条件的素数个数。第二行按照从小到大的顺序输出所有满足条件的素数,两个数之间用一个空格区分。样例输入1样例输出42 3 5 7
这道题挺简单的,本来自己是肯定能够想到平方根为界限的,我开始自己傻了吧唧的,想减少判断过程所需的时间,于是想要初始化的时候预处理出所有小于1000000000是否为素数的标记
结果估计初始化的过程就超时了。。。
直接贴代码了,这太简单了。。。
#include <iostream>#include <queue>#include <stdio.h>using namespace std;const int MAX = 1000000000;int n;queue<int> q;int m[10]={0};int coun = 0;bool OK(int k){ if(k <= 1) return false; for(int i = 2; i * i <= k; i++) { if(k%i == 0) return true; } return false;}void work(int i){ if(i == n) { int res = 0; for(int j = 0; j < n; j++) { res *= 10; res += m[j]; } if(OK(res)) { q.push(res); coun++; } return ; } if( i < n/2 || ( n%2!=0 && i < n/2+1 ) ) { for(int j = 0; j < 10; j++) { if(i == 0 &&((j == 0 || j == 2 || j == 5 || j == 4 || j == 6 || j == 8)&&n>1) ) { continue; } m[i] = j; work(i+1); } } else { m[i] = m[n-1-i]; work(i+1); }}int main(){ scanf("%d",&n); work(0); printf("%d\n",coun ); for(int i = 0; i < coun; i++) { int res = q.front(); q.pop(); printf("%d ", res); } printf("\n"); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。