质数判断 控制台版 (aardio 小程序)

最近发了几篇（我自认为）思辨性或哲理性较强的文章，不了解情况的访客可能以为这个博客已经转型了。所以，我赶紧发一篇带有强烈技术气息的文章吧。其实这篇文章今年4月的时候就应该要写了，还是拖到现在了。

这篇文章介绍《质数分解 控制台版》，这个也被我称为《质数判断0》，就是先前所发 VB 程序《质数判断》的控制台版，是我第一个 AAuto ——啊不—— aardio 小作。之所以做成控制台界面并不是因为用 aardio 编写图形界面程序麻烦（实际上一点也不），而是因为我对命令行有一种独特的情感（想想以前的 MyQQ 就一阵激动）。

0.1

发布日期：2014 年 11 月 3 日

算法基于《质数判断》3.5 版，此程序区别在于：

1. 无图形界面，取而代之的是控制台界面；
2. 显示了因数分解的过程，而不是只有结果；
3. 允许判断出质数/合数后中止过程，而不进行因数分解；
4. 增加了对外部参数调用的支持。

下载地址：程序 | 程序和源码

0.2

发布日期：2015年9月26日

该版更新在：

1. 改进核心算法，速度提升为原来的3倍（新算法在文章后面会说到）；
2. 增加了数是否为合数的初步判断；
3. 微调了文字格式和用户交互输入；
4. 修复了使用 jd 或 judge 命令而不给数导致崩溃的 BUG。

下载地址：程序 | 程序和源码

算法说明

在原来 VB 程序那篇文章中我已说过，“质数判断”实际上成了“因数分解”。通过尝试将一个数分解成几个质因数之和，来判断它是否是质数。

过去的算法是这样处理的：假设给定 51 这个数。程序首先用 2 除它，发现不可除断（51 不能整除 2）；于是用 3，除断得 17。将 17 作为要处理的数，用 2 除它，不可除断；用 3，不可除断，用 4，不可除断；不能用 5 了，因为已经大于 17 的平方根了。于是得出结果 17＝3×17。

或许你已经发现了，在上面的除法中，2 当除数后 4 又当了除数。那么问题来了，既然 2 都不能除断一个数，4 就能吗？明显不能。而当一个数的某一质因数比较大时，这样浪费资源的过程不知要重复多少次，像 2011，程序会用 2、3、4、5、6、7、8、…、44 去除它。用了 2、3、5 后还用 6、10、12、15、20、30 这些数是不是很蠢？为什么非得这样“加一加一”不可呢？就不能都拿质数去除吗？

这个还真不能。“加一加一”是为了方便程序生成除数，但是没有算法能让程序快速地生成全是质数的除数，因为质数并不具有我们想要的规律。难道要我将8位以内的质数都列出来保存，需要时读到内存？从程序体积、处理效率以及未来的扩展来看还是不可行吧。那么能不能退而求其次，发现一个简单的算法，让其能在列出所有质数的同时，尽可能地排除合数？转化为纯粹的数学问题就是，能不能得出一个有着比较简单的规律的数列，由数列的项构成的集合能较好地排除合数，而包含所有质数？

一次偶然的机会，我在一本教辅书上看到了素数（即质数）的性质：

1. 2是唯一的偶素数；
2. 没有比5大的素数能够以5结尾；
3. 在素数2，3，5，7之后，其他的素数必须以1，3，7，9结尾；
4. 如果将2和3以外的素数加上1或减去1，其结果必然是6的倍数。

后来被我概括为（下面换用“质数”概念表达）：

1. 6以内有且只有2，3，5是质数；
2. 6之后的质数必以1，3，7，9结尾；
3. 4以后的质数必然和6的某一倍数相邻。

根据这些性质——特别是我所概括的第3条性质——我们可以得到刚刚那个数学问题的一个好解。除了最小的那几个质数外，我们可以列出6的倍数的附近的数。鉴于加法运算比乘法运算快，我们应该找“乘以6、加1减1”的替代方案。于是我得出了一个从数5开始“加2加4”的数列（质数 2、3、5 单独列出），公式如下：

列出一些项看看：

2，3，5，7，11，13，17，19，23，25，29，31，35，37，41，43，47，49，53……

相比“2，3，4，5，6，7，…，50，51，52，……”那样是不是有了显著进步？用这个数列代替原来“加1加1”的数列，3月份的时候，我将它应用到了 0.2β版的《质数判断》。不过以 5 结尾的合数太多了，特别地排除一下。可以估算出，这些改进可使处理速度提升到原来的3倍。

最后再声明下，这个算法只是中学水平的哦。

项目地址

https://github.com/shansing/pnj0/