热退热退热

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;

/*
 * 素数环问题：将1~20排列成环，使得任意相邻两数之和为素数
 * 输入：无（n固定为20）
 * 输出：所有可行排列及总方案数
 */

bool b[21] = {0};     // 标记数字是否已使用（索引1~20）
int total = 0;        // 有效方案总数
int a[21] = {0};      // 存储当前排列（索引1~20）

int search(int t);    // 回溯生成排列的核心函数
int print();          // 输出当前有效排列
bool pd(int x, int y);// 判断x+y是否为素数

int main()
{
    search(1);        // 从第一个位置开始生成排列
    cout << total << endl; // 输出总方案数
    return 0;
}

/**
 * 递归生成排列并验证相邻数之和为素数
 * @param t 当前处理的位置（从1开始）
 * @return 无返回值，通过修改全局变量输出结果
 */
int search(int t)
{
    // 遍历所有可能数字（1~20）
    for (int i = 1; i <= 20; i++) {
        // 条件1：与前一个数的和为素数（当t>1时验证）
        // 条件2：当前数字未被使用
        if (pd(a[t-1], i) && (!b[i])) {
            a[t] = i;       // 记录当前数字到位置t
            b[i] = 1;       // 标记为已使用
            
            // 若已填满20个位置
            if (t == 20) {
                // 额外验证首尾和是否为素数
                if (pd(a[20], a[1])) {
                    print(); // 输出有效排列
                }
            } else {
                search(t + 1); // 递归处理下一个位置
            }
            
            b[i] = 0; // 回溯：释放当前数字
        }
    }
    return 0;
}

/**
 * 输出有效排列方案
 * @return 无返回值
 */
int print()
{
    total++; // 增加方案计数器
    
    // 格式化输出
    cout << "<" << total << ">"; // 输出方案序号
    for (int j = 1; j <= 20; j++) {
        cout << a[j] << " ";     // 输出排列数字
    }
    cout << endl;
}

/**
 * 判断两个数之和是否为素数
 * @param x 第一个数
 * @param y 第二个数
 * @return true-和为素数，false-和不是素数
 */
bool pd(int x, int y)
{
    // 特例处理：当处理第一个数时（t=1），无需验证
    if (x == 0) return true;
    
    int i = x + y;      // 计算和值
    int k = 2;
    // 素数判断优化：只需验证到平方根
    while (k <= sqrt(i) && (i % k != 0)) {
        k++;
    }
    // 若循环完整执行说明未找到因数
    return k > sqrt(i);
}

二五

er

菜包们试试个1000🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐

菜包们试试个1000🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♂️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️🧛‍♀️◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐◑﹏◐

#include<bits/stdc++.h>
using namespace std;
int a[100], book[100], n, ans = 0;
void dfs(int place)
{
    for(int i = 1; i <= n; ++i) {
        if(book[i] == 0) { //数字i没放入
            a[place] = i; //把i放入第place个盒子
            book[i] = 1; //标记
            dfs(place + 1); //递归下一个盒子
            book[i] = 0; //取消标记
        }
    }
    if(place == n + 1) {//到达最后一个盒子的下一个
        ans++; //总共的可能
        for(int i = 1; i <= n; ++i)
            cout<<a[i]<<" ";
        cout<<endl;
        return; //返回上一个盒子（最近一次调用dfs的地方）
        //return可去
    }
}
int main()
{
    cin>>n;
    dfs(1); //从第一个盒子开始
    cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[1000000], book[1000000], n, ans = 0;
void dfs(int place)
{
    for(int i = 1; i <= n; ++i) {
        if(book[i] == 0) { //数字i没放入
            a[place] = i; //把i放入第place个盒子
            book[i] = 1; //标记
            dfs(place + 1); //递归下一个盒子
            book[i] = 0; //取消标记
        }
    }
    if(place == n + 1) {//到达最后一个盒子的下一个
        ans++; //总共的可能
        for(int i = 1; i <= n; ++i)
            cout<<a[i]<<" ";
        cout<<endl;
        return; //返回上一个盒子（最近一次调用dfs的地方）
        //return可去
    }
}
int main()
{
    cin>>n;
    dfs(1); //从第一个盒子开始
    cout<<ans<<endl;
    return 0;
}