β

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

闪星空间 201 阅读

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

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

0.1

质数判断 0.1 界面

发布日期:2014 年 11 月 3 日

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

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

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

0.2

质数判断 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 单独列出),公式如下:

an=2(n=1),an=3(n=2),an=an-1+2(n=3或n是大于2的偶数),an=an-1+4(n是大于3的奇数)

列出一些项看看:

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/

作者:闪星空间
“闪闪的星”的独立博客,英文名“Shansing!”。我认为每个人都是一颗闪星,我只是闪星之一。让我们闪闪发光吧,终有一天这里会是闪星空间!
原文地址:质数判断 控制台版 (aardio 小程序), 感谢原作者分享。