搜索加各种剪枝，很悲剧写了N个小时还是超时，只好弃坑了。
（P.S. 谁能再告诉我一些优化思路。。。感激不尽。。。）
测试数据：
------- test 1 ----
11 2
------- test 2 ----
11 1
------- test 3 ----
17 7
------- test 4 ----
29 2
------- test 5 ----
19 8
------- test 6 ----
17 1
------- test 7 ----
19 5
------- test 8 ----
23 7
------- test 9 ----
23 1
------- test 10 ----
23 3
有毒的代码。。。。
#include <stdio.h>int sum; char isprime[100000]; int ptbl[10][10000];pgen(void) {int i;for(i=2; i<100000; ++i) {if (!isprime[i]) {if (i > 10000 &&i % 10 + (i/10 % 10) + (i/100 % 10) + (i/1000) % 10 + i/10000 == sum) {int c = i / 10000 % 10;ptbl[c][++ptbl[c][0]] = i;}int t;for(t=i+i; t<100000; t += i)isprime[t] = 1;}}for(i=0; i<10000; ++i) isprime[i] = 1; }// printf("-->%d\n", (a/10000 * 10000) + (b/1000 % 10) * 1000 + (c / 100 % 10) * 100 + (c / 10 % 10) * 10 + e % 10);//if (isprime[(a/10000 * 10000) + (b/1000 % 10) * 1000 + (c / 100 % 10) * 100 + (c / 10 % 10) * 10 + e % 10])int isok(int a, int b, int c, int d, int e, int p2[], int p3[], int p4[], int p5[]) {int p1[] = {a / 10000, b / 10000, c / 10000, d / 10000, e / 10000};#define p p2if (isprime[p[0] * 10000 + p[1] * 1000 + p[2] * 100 + p[3] * 10 + p[4]])return 0;#undef p#define p p3if (isprime[p[0] * 10000 + p[1] * 1000 + p[2] * 100 + p[3] * 10 + p[4]])return 0;#undef p#define p p4if (isprime[p[0] * 10000 + p[1] * 1000 + p[2] * 100 + p[3] * 10 + p[4]])return 0;#undef p#define p p5if (isprime[p[0] * 10000 + p[1] * 1000 + p[2] * 100 + p[3] * 10 + p[4]])return 0;int k1, k2, k3, k4, k5;k1 = p1[0], k2 = p2[1], k3 = p3[2], k4 = p4[3], k5 = p5[4];if (k1 + k2 + k3 + k4 + k5 != sum || isprime[k1 * 10000 + k2 * 1000 + k3 * 100 + k4 * 10 + k5])return 0;k1 = p1[4], k2 = p2[3], k3 = p3[2], k4 = p4[1], k5 = p5[0];if (k1 + k2 + k3 + k4 + k5 != sum || isprime[k1 * 10000 + k2 * 1000 + k3 * 100 + k4 * 10 + k5])return 0;#undef p#define p p1return p[0] * 10000 + p[1] * 1000 + p[2] * 100 + p[3] * 10 + p[4];#undef p }int ans[10000][5], index[10000], ansp;int qcmp(const void *a, const void *b) {if (ans[*(int *)a][0] > ans[*(int *)b][0])return 1;else if (ans[*(int *)a][0] == ans[*(int *)b][0]) {if (ans[*(int *)a][1] > ans[*(int *)b][1])return 1;else if (ans[*(int *)a][1] == ans[*(int *)b][1]) {if (ans[*(int *)a][2] > ans[*(int *)b][2])return 1;else if (ans[*(int *)a][2] == ans[*(int *)b][2]) {if (ans[*(int *)a][3] > ans[*(int *)b][3])return 1;else if (ans[*(int *)a][3] == ans[*(int *)b][3])if (ans[*(int *)a][4] > ans[*(int *)b][4])return 1;}}}return -1; }int main(void) { // freopen("prime3.in", "r", stdin); // freopen("prime3.out", "w", stdout);int a[5], b[5], c;scanf("%d%d", &sum, &b[0]);pgen(); // 生成素数表int t6[5], t7[5];for(c = 1; c <= ptbl[b[0]][0]; ++c) {b[1] = ptbl[b[0]][c] / 1000 % 10,b[2] = ptbl[b[0]][c] / 100 % 10,b[3] = ptbl[b[0]][c] / 10 % 10,b[4] = ptbl[b[0]][c] % 10;if (b[1] && b[2] && b[3]) {#define k 0for(a[k] = 1; a[k] <= ptbl[b[k]][0]; ++a[k]) {int t2[5], t3[5], t4[5], t5[5];int p2[5], p3[5], p4[5], p5[5];t6[k] = b[0];t2[k] = p2[k] = ptbl[b[k]][a[k]] / 1000 % 10;t3[k] = p3[k] = ptbl[b[k]][a[k]] / 100 % 10;t4[k] = p4[k] = ptbl[b[k]][a[k]] / 10 % 10;t5[k] = p5[k] = t7[k] = ptbl[b[k]][a[k]] % 10;if (ptbl[b[0]][a[0]] / 1000 % 10 &&ptbl[b[0]][a[0]] / 100 % 10 &&ptbl[b[0]][a[0]] / 10 % 10) {#undef k#define k 1for(a[k] = 1; a[k] <= ptbl[b[k]][0]; ++a[k]) {t2[k] = t2[k-1] + (t6[k] = p2[k] = ptbl[b[k]][a[k]] / 1000 % 10);t3[k] = t3[k-1] + (p3[k] = ptbl[b[k]][a[k]] / 100 % 10);t4[k] = t4[k-1] + (t7[k] = p4[k] = ptbl[b[k]][a[k]] / 10 % 10);t5[k] = t5[k-1] + (p5[k] = ptbl[b[k]][a[k]] % 10);t6[k] += t6[k-1], t7[k] += t7[k-1];if (t2[k] >= sum || t3[k] >= sum || t4[k] >= sum || t5[k] >= sum || t6[k] >= sum || t7[k] >= sum)continue;#undef k#define k 2for(a[k] = 1; a[k] <= ptbl[b[k]][0]; ++a[k]) {t2[k] = t2[k-1] + (p2[k] = ptbl[b[k]][a[k]] / 1000 % 10);t3[k] = t3[k-1] + (t7[k] = t6[k] = p3[k] = ptbl[b[k]][a[k]] / 100 % 10);t4[k] = t4[k-1] + (p4[k] = ptbl[b[k]][a[k]] / 10 % 10);t5[k] = t5[k-1] + (p5[k] = ptbl[b[k]][a[k]] % 10);t6[k] += t6[k-1], t7[k] += t7[k-1];if (t2[k] >= sum || t3[k] >= sum || t4[k] >= sum || t5[k] >= sum || t6[k] >= sum || t7[k] >= sum)continue;#undef k#define k 3for(a[k] = 1; a[k] <= ptbl[b[k]][0]; ++a[k]) {t2[k] = t2[k-1] + (t7[k] = p2[k] = ptbl[b[k]][a[k]] / 1000 % 10);t3[k] = t3[k-1] + (p3[k] = ptbl[b[k]][a[k]] / 100 % 10);t4[k] = t4[k-1] + (t6[k] = p4[k] = ptbl[b[k]][a[k]] / 10 % 10);t5[k] = t5[k-1] + (p5[k] = ptbl[b[k]][a[k]] % 10);t6[k] += t6[k-1], t7[k] += t7[k-1];if (t2[k] >= sum || t3[k] >= sum || t4[k] >= sum || t5[k] >= sum || t6[k] >= sum || t7[k] >= sum)continue;#undef k#define k 4for(a[k] = 1; a[k] <= ptbl[b[k]][0]; ++a[k]) {t7[k] = b[4];t2[k] = t2[k-1] + (p2[k] = ptbl[b[k]][a[k]] / 1000 % 10);t3[k] = t3[k-1] + (p3[k] = ptbl[b[k]][a[k]] / 100 % 10);t4[k] = t4[k-1] + (p4[k] = ptbl[b[k]][a[k]] / 10 % 10);t5[k] = t5[k-1] + (t6[k] = p5[k] = ptbl[b[k]][a[k]] % 10);t6[k] += t6[k-1], t7[k] += t7[k-1];if (t2[k] != sum || t3[k] != sum || t4[k] != sum || t5[k] != sum || t6[k] != sum || t7[k] != sum)continue;int p1;if (p1 = isok(ptbl[b[0]][a[0]],ptbl[b[1]][a[1]],ptbl[b[2]][a[2]],ptbl[b[3]][a[3]],ptbl[b[4]][a[4]], p2, p3, p4, p5)) {index[ansp] = ansp;ans[ansp][0] = ptbl[b[0]][a[0]],ans[ansp][1] = ptbl[b[1]][a[1]],ans[ansp][2] = ptbl[b[2]][a[2]],ans[ansp][3] = ptbl[b[3]][a[3]],ans[ansp][4] = ptbl[b[4]][a[4]];++ansp;/*printf("%d\n", p1);#define p p2printf("%d%d%d%d%d\n", p[0], p[1], p[2], p[3], p[4]);#undef p#define p p3printf("%d%d%d%d%d\n", p[0], p[1], p[2], p[3], p[4]);#undef p#define p p4printf("%d%d%d%d%d\n", p[0], p[1], p[2], p[3], p[4]);#undef p#define p p5printf("%d%d%d%d%d\n\n", p[0], p[1], p[2], p[3], p[4]);*/}}}}}}}}}if (ansp) {qsort(index, ansp, sizeof(int), qcmp);for(c=0; c<ansp; ++c) {if (c) printf("\n");printf("%d\n%d\n%d\n%d\n%d\n", ans[index[c]][0], ans[index[c]][1], ans[index[c]][2], ans[index[c]][3], ans[index[c]][4]);}} else printf("NONE");return 0; }
