素数方阵子问题——搜索的最少次数

  通过题意我们可以将各个点标为:

  (1,1)(1,2)(1,3)(1,4)(1,5)

  (2,1)(2,2)(2,3)(2,4)(2,5)

  (3,1)(3,2)(3,3)(3,4)(3,5)

  (4,1)(4,2)(4,3)(4,4)(4,5)

  (5,1)(5,2)(5,3)(5,4)(5,5)

  如果要在每一个点上枚举每一个数字,那么算法的时间复杂度至少为9^25(事实上更高),肯定会超时。

  考虑一下如下几条策略:

    1.因为行列对角线上的和是确定的,所以当行列或对角线上出现4个数时,就可以进行特判,剩下的一个数只需要一个减法就可以求出来。

    2.每个数的开头不能为0,即当纵坐标或横坐标为1时只需要搜索9次。

    3.对于每个数来说,其末位数字不能是0,2,4,5,6,8(因为以这几个数为结尾的五位数必定是合数),即当横坐标或纵坐标为5时只需要搜索4次。

    4.根据如上三条策略,我们可以将每个点的搜索次数用如下方阵表示(a代表10)

    

    5.既然搜索次数的矩阵已经出来了,那么具体的策略也就出来了:

      1)优先从需要搜索次数最少的点上开始搜索;

      2)存在许多点搜索次数相同时,优先搜索对角线上的点。

  根据策略5中的2条以及搜索次数的矩阵,大致可以得出以下搜索顺序:

  

  当然顺序不唯一。

原文地址:https://www.cnblogs.com/hinanawitenshi/p/6476422.html