程序员的算法趣题Q44: 质数矩阵

时间：12-31来源：作者：点击数：47

1. 问题描述

2. 解题分析

一共9个格子，每个格子都从{0,1,2,…,9}中可以任选数字的话，有10的9次方（10亿！）中可能的组合。就这样直接遍历的话会需要很长的时间，需要考虑缩小搜索范围的策略。

考虑9个格子中的数字（按行优先排列）分别记为a0, a1, …, a8。

由于质数肯定不能是偶数，所以个位数不能为{2,4,6,8}。同样也不能为5。因此a2,a5,a6,a7,a8的可选范围缩小为{1,3,7,9}。题设要求限定为三位质数，故首位数字不能为0，所以a0,a1,a2不能为0。只有a4的选择范围仍然为{0,1,2,…,9}，这样总的可能组合数缩小为：

仅为原始的10^9的(1/144)。

进一步，还可以利用early-stop的策略来提高搜索速度。因为总共有6个质数要考察，安排遍历的顺序使得可以尽量早地进行质数判断，如果发现不满足条件，就可以从某条搜索路径提前退出。比如说，已经安排了a0,a1,a2后，就可以先判断(a0,a1,a2)构成的三位数是否为质数；接下来，对a3,a6进行遍历，就可以对(a0,a3,a6)构成的三位数是否为质数进行判断。据此，考虑由外到内的遍历顺序为a0-a1-a2-a3-a6-a4-a5-a7-a8.

题设还要求质数不能重复。因此在以上遍历过程中，将搜索路径上得到的满足条件的质数记录下来，新的质数还要判断是否已经存在与该列表中，如果有不满足条件的也可以提前退出。这样做比把6个质数都凑齐了再判断是否有重复可能能够节约一些时间。在以下代码中，用一个list来实现一个stack(FIFO)，每得到一个新的满足条件的质数就加入到栈中；相应地，退回到上一层的时候要把本层加入到栈中的数要退出（因此代码中prime_lst.append()与prime_lst.pop()是成对出现的）。这个有点类似于深度优先搜索中的入栈退栈处理。因此本题解也可以用递归的方式实现，但是由于针对每个数的搜索范围不完全一致，所以递归方式也有点额外的麻烦。

以上其实也就是深度优先搜索的策略。。。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 27 07:40:05 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

def isPrime(n: int)->bool:
    if n == 1 or n == 2:
        return True    
    if n%2 == 0:
        return False

    for i in range(2, int(np.sqrt(n)) + 1):
   		if (n % i == 0):
   			return False
    return True    

prime_lst = [] # Used as a stack, oe LIFO
ans_cnt = 0
tStart = time.perf_counter()
for a0 in range(1,10):
    for a1 in range(1,10):
        for a2 in [1,3,7,9]:
            tmp = a0*100+a1*10+a2
            if not isPrime(tmp):
                continue
            prime_lst.append(tmp)
            for a3 in range(1,10):
                for a6 in [1,3,7,9]:
                    tmp = a0*100+a3*10+a6
                    if not (isPrime(tmp) and (tmp not in prime_lst)):
                        continue
                    prime_lst.append(tmp)
                    for a4 in range(0,10):
                        for a5 in [1,3,7,9]:
                            tmp = a3*100+a4*10+a5
                            if not (isPrime(tmp) and (tmp not in prime_lst)):
                                continue
                            prime_lst.append(tmp)
                            for a7 in [1,3,7,9]:
                                tmp = a1*100+a4*10+a7
                                if not (isPrime(tmp) and (tmp not in prime_lst)):
                                    continue
                                prime_lst.append(tmp)
                                for a8 in [1,3,7,9]:
                                    tmp = a2*100+a5*10+a8
                                    if (isPrime(tmp) and (tmp not in prime_lst)):
                                        prime_lst.append(tmp)
                                        tmp = a6*100+a7*10+a8
                                        if (isPrime(tmp) and (tmp not in prime_lst)):
                                            ans_cnt = ans_cnt + 1        
                                        prime_lst.pop()                     
                                prime_lst.pop()
                            prime_lst.pop()
                    prime_lst.pop()
            prime_lst.pop()                                    
tCost  = time.perf_counter() - tStart
print('ans_cnt={0}, tCost = {1:6.3f}(sec)'.format(ans_cnt,tCost))