1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 |
- #include <bits/stdc++.h>
-
- using namespace std;
- int visit[41];
- int prime[41];
- int n;
- int a[21];
- int b[21];
- int cut = 0;
- int flag = 0;
-
- void Prime() {
- //初始化都是素数
- for (int i = 2; i <= 40; i++) {
- if (!visit[i]) {
- prime[++prime[0]] = i; //纪录素数, 这个prime[0] 相当于 cnt,用来计数
- }
- for (int j = 1; j <= prime[0] && i * prime[j] <= 40; j++) {
- visit[i * prime[j]] = 1;
- if (i % prime[j] == 0) {
- break;
- }
- }
- }
- }
-
- void dfs(int k) {
- if (cut == 1) {
- return;
- }
- if (k == n + 1 && visit[a[1] + a[n]] == 0) {
- for (int i = 1; i <= n; i++) {
- cout << a[i] << " ";
- }
- cout << endl;
- cut++;
- } else {
- for (int i = 1; i <= n; i++) //***逐个尝试
- {
- if (b[i] == 0 && visit[i + a[k - 1]] == 0) //***i没用过且满足条件
- {
- a[k] = i; //***存储当前序列
- b[i] = 1; //****标记
- dfs(k + 1); //***递归
- b[i] = 0; //***去除标记
- }
- }
- }
- }
-
- int main() {
- Prime();
- memset(a, 0, sizeof(a[0]));
- memset(b, 0, sizeof(b[0]));
- cin >> n;
- dfs(1);
- if (cut == 0) {
- cout << "no solution" << endl;
- }
- return 0;
- }
-
|