思路与算法

先筛选指定数字和的所有五位质数，建立每种长度的合法前缀和后缀表。按行优先从小到大试数字，同时维护当前行、每列、主对角的前缀；反对角按输入顺序恰好是从右端向左补，因此检查合法质数后缀。五个方向的局部约束通过才递归。

正确性说明

任一合法方阵的每个已填写前缀或后缀都在相应表内，剪枝不会删除合法解。填满时每行、列及两对角均是筛出的五位质数，数字和一致且左上角指定，所以输出全部合法。每格按0至9枚举，行优先顺序就是25位字典序，不重不漏。

复杂度

筛与建立表O(100000loglog100000+5·100000)，DFS最坏可界为O(10^25)，实际由质数前后缀强剪枝。数组初始化O(6·100000)，空间O(100000+25+25A)，A为输出方阵数；不宣称搜索为多项式。

易错点

反对角要求从左到右读，即左下至右上，不能把上下方向反过来。五位数不允许前导0，前缀表自动限制首位；找不到输出NONE。方案间保留空行。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
bool pre[6][100000], suf[6][100000];
int g[25], col[5], pw[6] = {1, 10, 100, 1000, 10000, 100000}, first, S;
vector<string> ans;
void dfs(int at, int row, int dia, int anti) {
    if (at == 25) {
        string s;
        for (int x : g)
            s += char('0' + x);
        ans.push_back(s);
        return;
    }
    int r = at / 5, c = at % 5;
    for (int v = 0; v <= 9; v++) {
        if (at == 0 && v != first)
            continue;
        int nr = row * 10 + v, nc = col[c] * 10 + v, nd = dia, na = anti;
        if (!pre[c + 1][nr] || !pre[r + 1][nc])
            continue;
        if (r == c) {
            nd = dia * 10 + v;
            if (!pre[r + 1][nd])
                continue;
        }
        if (r + c == 4) {
            na = anti + v * pw[r];
            if (!suf[r + 1][na])
                continue;
        }
        int old = col[c];
        col[c] = nc;
        g[at] = v;
        dfs(at + 1, c == 4 ? 0 : nr, nd, na);
        col[c] = old;
    }
}
int main() {
    cin >> S >> first;
    vector<bool> comp(100000);
    for (int i = 2; i * i < 100000; i++)
        if (!comp[i])
            for (int j = i * i; j < 100000; j += i)
                comp[j] = true;
    for (int i = 10000; i < 100000; i++)
        if (!comp[i]) {
            int s = 0;
            for (int x = i; x; x /= 10)
                s += x % 10;
            if (s != S)
                continue;
            for (int k = 1; k <= 5; k++) {
                pre[k][i / pw[5 - k]] = true;
                suf[k][i % pw[k]] = true;
            }
        }
    dfs(0, 0, 0, 0);
    if (ans.empty())
        cout << "NONE\n";
    for (int a = 0; a < (int)ans.size(); a++) {
        if (a)
            cout << '\n';
        for (int i = 0; i < 25; i += 5)
            cout << ans[a].substr(i, 5) << '\n';
    }
}