1031 質數環：DFS 回溯搜索全排列 (N≤17)

題目規則

大小 N (N≤17) 的質數環由 1~N 組成環，相鄰兩數之和為質數。第一個數固定為 1。按字典序輸出所有本質不同的環。例如 N=6 輸出：

1 4 3 2 5 6
1 6 5 2 3 4

暴力 DFS 可行性分析

• N≤17，最多 16! ≈ 2×10^13，但質數約束極強，實際搜索空間極小
• 預計算 2~34 以內質數表，O(1) 判斷
• 回溯時剪枝：當前選數與前一數和非質數則跳過
• 最後檢查尾首相連是否為質數

核心代碼框架

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

int a[18], n, b[18]; // a:可選數, b:已放數

bool isPrime(int x) {
    for (int i=2; i<=sqrt(x); i++) if (x%i==0) return false;
    return true;
}

void dfs(int pos) {
    if (pos == n) {
        if (isPrime(b[n-1] + 1)) { // 尾首相連
            for (int i=0; i

關鍵優化

質數表預計算避免重複開根號
按遞增順序嘗試可選數，天然保證字典序輸出
N=17 時運行極快，典型 DFS 剪枝應用