题目描述 Description
农民约翰的母牛总是产生最好的肋骨。 你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。 农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。 写一个程序对给定的肋骨的数目 N(1<=N<=8),求出所有的特殊质数。 数字1不被看作一个质数。
输入描述 Input Description
单独的一行包含N。
输出描述 Output Description
按顺序输出长度为 N 的特殊质数,每行一个。
样例输入 Sample Input
4
样例输出 Sample Output
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
数据范围及提示 Data Size & Hint
见描述
神奇的特性：特殊质数的首位只有2 3 5 7四种可能，其他位只有1 3 7 9四种可能~
然后这道题就变成了每次只有四种可能的深搜~而且数据范围<=8也很小~
判断质数从2开始循环啊啊啊啊！我自己都数不清是第几次因为这个检查到吐血了！
#include<cstdio>
#include<cmath>int n,a1[5]={0,2,3,5,7},a2[5]={0,1,3,7,9},tot;bool pan(int u)
{for(int j=2;j<=(int)sqrt(u*1.0);j++)if(u%j==0) return 0;return 1;
}void dfs(int u,int v)
{if(n==v){printf("%d\n",u);return;}for(int ii=1;ii<=4;ii++)if(pan(u*10+a2[ii])) dfs(u*10+a2[ii],v+1);return;
}int main()
{scanf("%d",&n);if(n==1){for(int i=1;i<=4;i++) printf("%d\n",a1[i]);return 0;}for(int i=1;i<=4;i++) dfs(a1[i],1);return 0;
}