题目链接：https://www.yuque.com/mostshadowless/vx1lfh/ghwtxo#wTuap

题目分析：题目要求很明确，就是需要我们填充 5 * 5的矩阵，使其满足行、列、对角线均为素数，且每行、每列、主副对角线的数字和等于题目给定的值。难点在于如何把时间复杂度降下来，单纯的暴力搜索绝对不行。特别是需要我们去考虑如何在搜索的过程中剪枝。

解题步骤：

  1. 因为题目要求的是5位的素数，意味着其范围为 10000 ~ 99999，因为在搜索的过程中需要频繁的判断当前尝试的组合是否为素数，所以在进行搜索前，我们先预处理生成 100000 以内的素数，然后在搜索的过程中可以直接利用。在求解素数的过程中，还利用了埃式筛法加速[1, 100000]内素数的求解。

下面利用代码进一步展示细节。

  1. //求解[1, N]的素数
  2. public static final int N = 100010;
  4. //判断当前数字 i 是否为素数
  5. public static boolean[] isPrime = new boolean[N];
  7. //若当前数字 i 为素数，存储其前后缀
  8. //例如 i = 11351 为素数
  9. //且有前缀为:1, 11, 113, 1135, 11351
  10. //后缀为1, 51, 351, 1351, 11351
  11. //之所以需要记录这些前缀，是因为利用前后缀进行剪枝，如果当前搜索得到的前后缀不是这些素数所拥有的前后缀，
  12. //必然是不符合条件的，直接剪枝
  13. public static boolean[] lSum = new boolean[N];
  14. public static boolean[] rSum = new boolean[N];
  16. //存储素数，以及素数的个数
  17. public static int cnt = 0;
  18. public static int [] prime = new int[N];
  21. //欧拉筛选素数
  22. public static void euler(){
  23.     //初始化
  24.     Arrays.fill(isPrime, true);
  25.     isPrime[0] = false;
  27.     for(int i = 2; i < N; i++){
  28.         if(isPrime[i]){
  29.             //记录这个素数
  30.             prime[cnt++] = i;
  32.             //计算当前素数各位置数字和
  33.             int temp = i, t = 0;
  34.             while(temp != 0){
  35.                 t = t + temp % 10;
  36.                 temp /= 10;
  37.             }
  39.             //同时处理所有前后缀的质数(必须是各位置数字和等于S的素数)
  40.             if(i > 10000 && i < 100000 && t == S){
  41.                 lSum[i / 10000] = lSum[i / 1000] = lSum[i / 100] = lSum[i / 10] = lSum[i] = true;
  42.                 rSum[i % 10000] = rSum[i % 1000] = rSum[i % 100] = rSum[i % 10] = rSum[i] = true;
  43.             }
  44.         }
  45.         //素数的倍数必然不是素数，提前排除
  46.         for(int j = 0; j < cnt && i * prime[j] < N; j++){
  47.             isPrime[i * prime[j]] = false;
  48.             if(i % prime[j] == 0){
  49.                 break;
  50.             }
  51.         }
  52.     }
  53. }
  1. 接下来就是进行搜索，搜索的顺序是从左往右，从上往下，简单的说，就是依次填充第一行的位置，然后填充第二行的位置，依次类推。

在搜索的过程中，需要记录当前行对应的数字，以及到当前搜索位置列的累加情况，分别对应代码中的 row[] 和 col[]。
同时，还有记录主副对角线的取值情况。

  1. //存储素数矩阵
  2. public static int[][] arr = new int[5][5];
  4. //存储当前搜索位置累计的行的数字
  5. public static int[] row = new int[5];
  7. //存储当前搜索位置累计的列的数字
  8. public static int[] col = new int[5];
  10. //存储当前搜索位置主副对角线的位置
  11. public static int line1, line2;
  13. //权数组，为了方便副对角线的取值
  14. public static int[] pow = {1, 10, 100, 1000, 10000};
  16. //所有满足条件的方案数
  17. public static int total = 0;
  19. public static void dfs(int r, int c){
  20.     if(c == 5){ //代表这一行已经搜索完成，转至下一行第一列开始搜索
  21.         r = r + 1;
  22.         c = 0;
  23.     }
  24.     if(r == 5){ //代表搜索完成，得到一种分配方案
  25.         total++;
  26.         if(total != 1){ //答案格式要求，每个方案空一行
  27.             System.out.println();
  28.         }
  29.         for(int i = 0; i < 5; i++){ //输出结果
  30.             System.out.println(row[i]);
  31.         }
  32.         return;
  33.     }
  34.     boolean[] flag = new boolean[4];
  35.     for(int i = 0; i < 10; i++){
  36.         //当前行
  37.         flag[0] = lSum[row[r] * 10 + i];
  38.         //当前列
  39.         flag[1] = lSum[col[c] * 10 + i];
  40.         //当前正对角线
  41.         flag[2] = (r != c) || (r == c && lSum[line1 * 10 + i]);
  42.         //当前副对角线
  43.         flag[3] = (r + c != 4) || (r + c == 4 && rSum[line2 + i * pow[r]]);
  45.         //如果上述四个条件有任意一个不满足，则剪枝
  46.         if(!(flag[0] && flag[1] && flag[2] && flag[3])){
  47.             continue;
  48.         }
  50.         //放置i
  51.         row[r] = row[r] * 10 + i;
  52.         col[c] = col[c] * 10 + i;
  53.         if(r == c){ //主对角线
  54.             line1 = line1 * 10 + i;
  55.         }
  56.         if(r + c == 4){ //副对角线
  57.             line2 = line2 + i * pow[r];
  58.         }
  60.         dfs(r, c + 1); //搜索当前行的下一列
  62.         //恢复i
  63.         row[r] /= 10;
  64.         col[c] /= 10;
  65.         if(r == c){
  66.             line1 /= 10;
  67.         }
  68.         if(r + c == 4){
  69.             line2 %= pow[r];
  70.         }
  71.     }
  72. }

完整代码

import java.lang.reflect.Array;
import java.util.*;

public class Test{
    public static final int N = 100010;
    public static boolean[] isPrime = new boolean[N];
    public static boolean[] lSum = new boolean[N];
    public static boolean[] rSum = new boolean[N];

    //存储素数，以及素数的个数
    public static int cnt = 0;
    public static int [] prime = new int[N];

    //S:每行，每列，主副对角线元素之和需要等于S
    //A:左上角元素取值（题目给定）
    public static int S, A;

    //存储素数矩阵
    public static int[][] arr = new int[5][5];

    public static int[] row = new int[5];
    public static int[] col = new int[5];

    public static int line1, line2;

    public static int[] pow = {1, 10, 100, 1000, 10000};

    //所有满足条件的方案数
    public static int total = 0;

    //欧拉筛选素数
    public static void euler(){
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        for(int i = 2; i < N; i++){
            if(isPrime[i]){
                prime[cnt++] = i;
                int temp = i, t = 0;
                while(temp != 0){
                    t = t + temp % 10;
                    temp /= 10;
                }

                //同时处理所有前后缀的质数
                if(i > 10000 && i < 100000 && t == S){
                    lSum[i / 10000] = lSum[i / 1000] = lSum[i / 100] = lSum[i / 10] = lSum[i] = true;
                    rSum[i % 10000] = rSum[i % 1000] = rSum[i % 100] = rSum[i % 10] = rSum[i] = true;
                }
            }
            for(int j = 0; j < cnt && i * prime[j] < N; j++){
                isPrime[i * prime[j]] = false;
                if(i % prime[j] == 0){
                    break;
                }
            }
        }
    }
    public static void dfs(int r, int c){
        if(c == 5){
            r = r + 1;
            c = 0;
        }
        if(r == 5){
            total++;
            if(total != 1){
                System.out.println();
            }
            for(int i = 0; i < 5; i++){
                System.out.println(row[i]);
            }
            return;
        }
        boolean[] flag = new boolean[4];
        for(int i = 0; i < 10; i++){
            //当前行
            flag[0] = lSum[row[r] * 10 + i];
            //当前列
            flag[1] = lSum[col[c] * 10 + i];
            //当前正对角线
            flag[2] = (r != c) || (r == c && lSum[line1 * 10 + i]);
            //当前副对角线
            flag[3] = (r + c != 4) || (r + c == 4 && rSum[line2 + i * pow[r]]);

            //如果上述四个条件有任意一个不满足，则剪枝
            if(!(flag[0] && flag[1] && flag[2] && flag[3])){
                continue;
            }

            //放置i
            row[r] = row[r] * 10 + i;
            col[c] = col[c] * 10 + i;
            if(r == c){
                line1 = line1 * 10 + i;
            }
            if(r + c == 4){
                line2 = line2 + i * pow[r];
            }

            dfs(r, c + 1);

            //恢复i
            row[r] /= 10;
            col[c] /= 10;
            if(r == c){
                line1 /= 10;
            }
            if(r + c == 4){
                line2 %= pow[r];
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        A = sc.nextInt();

        euler();

        for(int i = 0; i < 5; i++){
            Arrays.fill(arr[i], -1);
        }

        arr[0][0] = A;

        row[0] = col[0] = line1 = A;

        dfs(0, 1);

        if(total == 0){
            System.out.println("NONE");
        }

    }
}