特殊的质数肋骨
题目描述：农民约翰确定他卖给买方的是真正的质数肋骨，是因为从右边开始依次取走肋骨，每次还剩下的肋骨上的数字都组成一个质数。举例来说：7 3 3 1 全部肋骨上的数字 7331 是质数；三根肋骨 733 是质数；二根肋骨 73 是质数；当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。写一个程序对给定的肋骨的数目 n，求出所有的特殊质数。1 不是质数。
可以用深度优先搜索来写这道题：
<?php echo 'hello world!'; ?>
如果不会深搜该怎么办？试着分析一下：首先第一位（最高位）肯定是2、3、5、7四个中的一个。其次接下来的每一位都只能在1、3、5、7、9中选择。这样能不能用枚举来实现呢？
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
bool isPrime(int n);
int main()
{
int n;
cin >> n;
//最高位只能是2、3、5或7
q.push(2);
q.push(3);
q.push(5);
q.push(7);
for (int i = 2; i <= n; i++)
{
int len = q.size();
for (int j = 0; j < len; j++)
{
int h = q.front() * 10;
if (isPrime(h + 1))
q.push(h + 1);
if (isPrime(h + 3))
q.push(h + 3);
if (isPrime(h + 5))
q.push(h + 5);
if (isPrime(h + 7))
q.push(h + 7);
if (isPrime(h + 9))
q.push(h + 9);
q.pop();
}
}
int len = q.size();
for (int i = 0; i < len; i++)
{
cout << q.front() << endl;
q.pop();
}
return 0;
}
bool isPrime(int n)
{
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}