农民约翰的母牛总是产生最好的肋骨。 你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。 农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 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[4] = { 1, 3, 7, 9 }; int n; LL mulmod(LL a, LL b, LL p) { LL d = 1; a = a%p; while (b>0) { if (b & 1) d = (d*a) % p; a = (a*a) % p; b >>= 1; } return d; } bool witness(LL a, LL n) { LL d = n - 1; if (n == 2) return true; if (!(n & 1)) return false; while (!(d & 1)) d = d / 2; LL t = mulmod(a, d, n); while ((d != n - 1) && (t != 1) && (t != n - 1)) { t = mulmod(t, 2, n); d = d << 1; } return (t == n - 1) || (d & 1); } bool isprime(LL n) { int a[3] = { 2, 7, 61 }; for (int i = 0; i<3; i++) if (!witness(a[i], n)) return false; return true; } void dfs(int x, int m) { if (x == n){ printf("%d ", m); return; } for (int i = 0; i < 4; ++i) { if (isprime(m * 10 + num[i])){ dfs(x + 1, m * 10 + num[i]); } } } int main() { scanf("%d", &n); dfs(1, 2); dfs(1, 3); dfs(1, 5); dfs(1, 7); }