基于Java Map的素数方阵求解优化

雷育铭

（清远职业技术学院信息技术与创意设计学院，广东 清远 511510）

1 引言

在基于Java集合类求解素数方阵的过程中[1]，笔者发现：以HashSet为例，方阵阶数每增长一阶，在同一环境下算法运行时间增长10倍以上。就1亿个组合测试时间来看，7阶的运行时间超过15小时，如下表所示：

其中，A集合包含所有N位的可逆素数，B集合为A集合中不包含偶数和5的所有素数。

为了解决此问题，笔者通过精简集合样本数、从数字拆分中删除new操作、加快方阵旋转、使用映射替换集合以及检测与消除无效组合等手段，对引文[1]中的算法进行了大幅优化，最终使得运行时间在7阶时能够缩短2200多倍，降为23秒左右。

2 精简集合样本数

N阶素数方阵的求解，基本思路是先取样组合后枚举测试，主要规则、步骤为：①筛选N位可逆素数构成A集合，在A集合中继续筛选不含偶数和5的可逆素数构成B集合；②循环从B集合取两个不同的素数分别放首尾两行，从A集合取N-2个不同的素数放中间的N-2行，组合成初始方阵M；③判断方阵M是否为目标方阵（即M的各列和两条对角线任意方向上的N位数均构成一个N位可逆素数），如果不是，则返回②；④判断M是否与已有的目标方阵相似，如果是，直接返回②；⑤如果不是，则添加M到目标方阵集合，返回②。流程如下：

经过观察分析，B集合中的可逆素数是成对存在的，比如4位可逆素数1193和它的逆序素数3911同时存在。考虑到每个目标方阵同样具有方向可逆性[1]，因此可以规定M的首行只需从B集合每对互逆的素数中的较小者中取样即可，这些较小者构成的集合记为C集合。……