「CODEVS2080」特殊的质数肋骨
题目描述
农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说:7 3 3 1全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。
输入
单独的一行包含N。
输出
按顺序输出长度为 N 的特殊质数,每行一个。
样例输入
4
样例输出
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
提示
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<iostream> #include<math.h> using namespace std; int n1[4]={2,3,5,7}; int n2[4]={1,3,7,9}; int n; bool pd(int x) { for (int i=2;i<=(int) sqrt(x*1.0);i++) if (x%i==0) return false; return true; } void search(int s,int i) { if(i==n){cout<<s<<endl;return;} int ss; for(int j=0;j<4;j++) { ss=s*10+n2[j]; if(pd(ss)) search(ss,i+1); } } int main() { cin>>n; if (n==1) cout<<2<<endl<<3<<endl<<5<<endl<<7; else {for(int i=0;i<4;i++) search(n1[i],1);} return 0; } |
Subscribe
计数器 9794926
OI 课件=>
OI 课件=>