关于如何寻找质数的一种尝试

易照雄

摘  要：从小于20的八个已知质数出发，由数值计算去尝试寻找质数（包括孪生质数）的公式与简便方法。

关键词：质数;伪质数;贋质数;数值计算

一、关于质数的公式

质数（或称之为素数）是指只能被1和其自身所整除的自然数。而合数则是指通过若干个质数相乘所构成的、可以被拆分的自然数。正是在这个意义上，人们将质数视为数学中的“原子”-------一切数的基础。通过考察已知的質数不难看出，所有两位及两位以上的质数的个位数只能是1、3、7、9，无一例外。而个位数为0、2、4、5、6、8的自然数以及开方后为整数的自然数，均无一例外为合数。数值计算表明，所有大于10的质数似都可以由公式   给出。只不过该公式在给出所有质数的同时也给出了相当数量的合数，并不全都是质数。实际上，质数也仅仅只是其中的一部分甚至是一小部分而已。这里，当我们把自然数 代入该公式后，如果得到的 值为整数，我们就说自然数 可以通过“ ”测试。而由此得到的自然数 ，我们则称之为 “ ”质数。我们也可以将公式 ， 改写成   ，这样的公式包含了10以内的四个质数：2、3、5、7。至于2x3重复出现了两次，牵强的解释可能是由2、3可以构建5和7，因而2、3显得比5和7更具基础性一些。

下面由公式 ， 来尝试寻找200以内的质数。我们先给出由这两个公式所得到的计算值（这里，n=0、1、2、3……）：

将以上的计算值排列如下：

5  7  11 13  17  19  23  25  29  31  35  37  41  43  47  49  53  55  59  61  65  67  71  73  77  79  83  85  89  91  95  97      101  103  107  109  113  115  119  121  125  127  131  133  137  139  143  145  149  151  155  157  161  163  167  169  173  175  179  181  185  187  191  193  197  199

以上所列出的全部计算值已经包括了200以内的所有质数，当然也还包括一定数量的非质数。如何去掉那些非质数是我们这里要找寻质数的关键。我们都知道费马小定理：如果n是一个质数的话，那么对于任意的一个数 ， 的n次方减去之 后都将是n的倍数。也即 。这样，我们可以通过应用基于费马小定理的费马素性测试，做到去掉上面所列的自然数中的非质数。不过 大都是非常大的数，这给通常的计算及素性测试带来比较大的麻烦和不便。

本文所给出如下一个比较繁琐但却似乎行之有效的方法，也有可能做到去掉上面的非质数，也即我们仿照远古时候找寻质数的“筛法”：（1）按20以内的已知质数从5开始，按由小到大的顺序，先去掉与5 相关的合数：5x5=25，5x7=35，5x11=55，5x13=65，5x17=85，5x19=95（限于100以内的自然数）和进一步的5x23=115，5x25=125，5x29=145，5x31=155，5x35=175，5x37=185（限于200以内的自然数），或者更简便的就是直接去掉上面所列的计算值中个位数为5的数-------25、35、55、65、85、95和115、125、145、155、175、185;（2）再依次去掉7x7=49，7x11=77，7x13=91（同样限于100以内的自然数）和7x17=119，7x19=133，7x23=161，7x25=175以及 11x11=121，11x13=143，11x17=187和13x13=169（同样限于200以内的自然数）。再将这样的计算值排列如下：

25  35  49  55  65  77  85  91  95  115  119  121  125  133  143  145

155  161  169  175  185  187

很显然，上面的值均为非质数，且全都已经包括在前面的计算值中。将前面的计算值中的上述非质数全都去掉，这样，我们就得到了200以内的除2和3以外的所有质数：

5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97     101  103  107  109  113  127  131  137  139  149  151 157  163  167  173  179  181  191  193  197  199

由上面的讨论可知，部分个位数为1、3、7、9的自然数，实际上并不是质数，而是一大类可以通过 “ ”测试的合数，如91、143、187、169，我们暂且将这类仍属于“ ”质数的自然数称之为伪质数。通过依次并连续运用上面（1）、（2）那样的方法，就可以去掉所有类似的非质数（包括伪质数）。这里，我们把建立在公式 和 的基础上并进一步"筛掉"所有非质数的方法，暂且称之为"新筛法"-------（a）從5和7的平方开始，之后为5与7相乘以及5和7与所有的“ ”质数依次相乘;（b）从11的平方开始，11再同样依次和其后所有的“ ”质数依次相乘;其后依次是13、17、19......，再去掉以上所有相应的计算值。通过这样的"新筛法"，我们就有可能筛掉公式 ， 所带来的包括伪质数在内的所有的非质数，最终找到我们所要找寻的质数。不难看出，随着n的增大，一方面给出了真实的质数，同时也给出了越来越多必须被筛掉的非质数，从而导致最终实际存在的质数越来越稀少。

二、贋质数公式

另外一大类不能通过上面的 “ ”测试的自然数，如21、87、117、141、177、561、1023、16383、10234029，其个位数也是1、3、7、9，这和前面的伪质数相同。因其仍然为合数，所以我们暂且称之为贋质数。贋质数可由两个连续的“ ” 质数的算术均数中来得到，且所有的贋质数都可以被3整除，也即被称为贋质数的这类合数都具有最小的质因数3，或者说两个n值不同但连续的“ ”质数之和都可以被6整除。即：

这也是另外形式的与质数密切相关的计算公式。

相较于其他类似的公式，在n=1、2、3……的情形下，如上面的 ，（这个公式给出的最小的质数为3，）， （其给出的最小的质数为5）以及 （其给出的最小的质数为11）， （其给出的最小的质数也为11）和    （这两个公式给出的最小的质数7为和5），还有三百多年前著名的法国业余数学家费马发现的质数相关公式      （这两个公式给出的最小的质数为5和7），公式 ， 给出的计算值不但不包括任何偶数（    这两个公式的计算值就包含部分偶数），也不包括任何贋质数，且所包含的非质数也是这类公式中最少的。若干个“ ” 质数相乘之后仍能通过“ ”测试（也即这样的乘积仍是一个伪质数）。

孪生质数（即双生质数）在公式 ， 中的都具有同一个n值。先“筛掉”与其取相同n值的非质数及质数（或质数及非质数）：如25以及与25取相同n值3的质数23，185以及与185取相同n值30的伪质数187，91以及与91取相同n值14的质数89;再“筛掉”孪生伪质数，如119和121。经过这样的筛选（也即筛掉所有的非质数以及取同一n值的质数），剩下来的就全都是孪生质数了。

三、计算质数和伪质数以及贋质数的公式   （k=0、1、2、3。。。。。。）

从上面我们所探讨的还不难看出，对于个位数是1、3、7、9的自然数，似可以分成三大类：质数、能通过“ ”及“ ”测试的伪质数以及不能通过“ ”及“ ”测试的贋质数，伪质数和贋质数本质上都是合数。这里，我们也可以给出包括了质数、伪质数及贋质数的公式 。我们可以先给出100以内的相应计算值：

另外显而易见是，如果我们说质数是一切数的 “原子”，合数是由若干个质数相乘得到的，那么公式    （n=1、2、3……）似乎也表明，2和3可能是所有大于等于5的质数的“原子”，也即任意一个大于等于5的质数都是由若干个2和3相加来构成的。还有，5和7出现在前面去掉非质数的"新筛法"中，也即5和7都参与“ ” 质数中的部分非质数的构建，但2和3却没有出现前面去掉非质数的"新筛法"中。另外，如果取n=0、1、2、3。。。。。。，则上面的公式 和    所给出的最小计算值分别为5、7和9。这些似乎都说明了2和3在质数中的基础性地位和与作用。

以小于20的八个质数尤其是三对孪生质数（5和7、11和13、17和19）为基础，应用本文以上所给出的寻找质数的"新筛法"，就可以很容易得到100以内的所有质数。在这个新的基础上似可以找到小于任意一个自然数（比如本文中的200）的所有质数，这至少在原则上来讲是可行的和可能的。至于识别任意一个自然数是否为质数或伪质数，我们在这里并不能给出类似基于费马小定理的费马素性测试那种简单有效的方法。我们只知道个位数为0、2、4、5、6、8的自然数及贋质数（其个位数为1、3、7、9）都不是质数。尽管我们在原则上似可以“筛掉”所有的伪质数，但这里并没有给出能判定任意一个个位数是1、3、7、9的自然数是否为质数或伪质数的简便方法。

总之，用以上这些只涉及初等数学的想法与方法去探讨和对待在自然数中寻找质数这样的老问题，也许是很有趣的，但这样的尝试是否正确和有意义则只能由相关的专家学者去评判了。

参考文献

[1]  陈仁政著  《说不尽的 》  科学出版社  2005年

[2] （英）马库斯.杜.索托伊著  柏华元译 《悠扬的素数》 人民邮电出版社 2019年