任务描述
本关任务:把从 1 到 n 这 n 个数摆成一个环,要求相邻的两个数的和是一个素数。
测试输入:
20
预期输出:
围成的圈是:1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
1-n个数的素数环往往有多种排列方案,该题目只要求输出第一种,想输出一种或者全部,控制一下条件就行
#include<stdio.h>
#include<math.h>
int a[40] = { 0,1 }, n, isPrime[40], vis[40] = { 0,1 }, flag = 0;
void dfs(int x, int op)
{
if (flag) return;//题目要求,只要输出第一种即可,后面的不用再输出了
if (flag == 0&&x == n + 1 && isPrime[a[n] + a[1]])//如果是第一次且排完且首位相加依旧满足素数,输出
{
flag++;
printf("围成的圈是:");
for (int i = 1; i < n; i++)printf("%d ", a[i]);
printf("%d\n", a[n]);
return;
}
for (int i = op; i <= n; i += 2) {//只搜奇数或偶数
if (!vis[i] && isPrime[i + a[x - 1]])
{
a[x] = i;
vis[i] = 1;
dfs(x + 1, op ^ 3);//位运算,1^3变为2,2^3变为1,用以保证相邻两个数为一奇一偶
vis[i] = 0;
}
}
}
int main()
{
int i, j;
for (i = 2; i < 40; i++) isPrime[i] = 1;
for (i = 3; i < 40; i++) {//素数筛选
for (j = 2; j < i / 2 + 1; j++) {
if (i % j == 0) {
isPrime[i] = 0;
break;
}
}
}
scanf("%d", &n);
dfs(2,2);
return 0;
}