农民约翰的母牛总是产生最好的肋骨。 你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。 农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。 写一个程序对给定的肋骨的数目 N(1<=N<=8),求出所有的特殊质数。 数字1不被看作一个质数。
思路：第一个数字肯定是2，3，5，7. 那么后面的数字都是在1，3，7，9中寻找的，就是一个简单的搜索。那怎么判断是否为素数，我直接用了米勒拉宾判断。
#include<cstdio>
#include<iostream>
typedef long long LL;
using namespace std;
int num[] = { , , , };
int n; LL mulmod(LL a, LL b, LL p) { LL d = ; a = a%p; while (b>) { if (b & ) d = (d*a) % p; a = (a*a) % p; b >>= ; } return d; } bool witness(LL a, LL n) { LL d = n - ; if (n == ) return true; if (!(n & )) return false; while (!(d & )) d = d / ; LL t = mulmod(a, d, n); while ((d != n - ) && (t != ) && (t != n - )) { t = mulmod(t, , n); d = d << ; } return (t == n - ) || (d & ); } bool isprime(LL n) { int a[] = { , , }; for (int i = ; i<; i++) if (!witness(a[i], n)) return false; return true; }
void dfs(int x, int m)
{
if (x == n){
printf("%d\n", m); return;
}
for (int i = ; i < ; ++i)
{
if (isprime(m * + num[i])){ dfs(x + , m * + num[i]); }
}
}
int main()
{
scanf("%d", &n);
dfs(, );
dfs(, );
dfs(, );
dfs(, );
}