我的书签
添加书签
移除书签2.2 孪生素数
我们知道，素数在自然数中的比例很少，而孪生素数就更少了。那么，什么是孪生素数？孪生素数有什么特点呢？
2.2.1 什么是孪生素数
所谓孪生素数，是指间隔为2的相邻素数，它们之间的距离已经近得不能再近了，就像孪生兄弟一样，因此被称为孪生素数，也称为双生素数。
例如，素数3和5，其间距为2，就是一组孪生素数。100以内的孪生素数还有5与7，11与13，17与19，29与31，41与43，59与61，71与73。
100以内的孪生素数共有8对，不过，随着数字的增大，孪生素数的分布变得越来越稀疏，寻找孪生素数也变得越来越困难。那么会不会在超过某个界限之后就再也不存在孪生素数了呢？
2.2.2 孪生素数的公式
对于自然数Q与Q＋2，若都不能被小于的任何素数整除，则Q与Q＋2就构成一对孪生素数。这句话可以用以下公式表达：
以上公式中，P1、P2、Pk表示从小到大的顺序素数2、3、5、7……，Bi≠0且Bi≠Pi－2，若Q＜（PK＋1）2－2，则Q与Q＋2是一对孪生素数。也就是说，将数Q分解后，最小剩余不能为0和Pi-2，例如Q不能是2M，3M＋1，5M＋3，7M＋5……，PiMi－2，否则Q＋2就是合数。
看一个例子吧。假设Q＝29，可分解为以下算式：
由于的结果取整后为5，因此，在上式中只按公式分解到5为止，一共有3项（即k＝3），且每项的B值都不为0，且Bi的每一项不等于Pi－2。因此，可得到29与29＋2是一对孪生素数。
上式也可使用同余式来表达：
根据中国剩余定理，对于给定的余数，在除数为素数的范围内有唯一的解。例如在上式中，除数为2、3、5时余数也知道了，因此就可以推算出Q的值为29。
2.2.3 中国剩余定理
什么是中国剩余定理呢？先来看一则中国民间的传说故事——“韩信点兵”。
秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足500，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步紧逼，楚军乱作一团。交战不久，楚军大败而逃。
韩信是怎么知道军队有1073名士兵的呢？
对于这个问题，可将其描述为一个数学问题，就是：一个数除以3余2，除以5余3，除以7余2，求这个数是多少？
先列出除以3余2的数：
再列出除以5余3的数：
在这两列数中，首先出现的公共数是8，3与5的最小公倍数是15，两个条件合并成一个就是：
将n分别取1、2、3、……即可得到数列：
再列出除以7余2的数：
可以看出，符合题目条件的最小数是23。
也就是说，我们已把题目中三个条件合并成一个：该数除以105余23。
由于汉军原有士兵1500人，死伤四五百人，即剩余的士兵应为1000余人，即可得到士兵的总数：
2.2.4 孪生素数分布情况
我们知道，素数本身的分布是随着数字的增大而越来越稀疏，不过幸运的是，早在古希腊时代，欧几里得（Euclid）就证明了素数有无穷多个。长期以来人们猜测孪生素数也应该有无穷多组，可是该怎么验证这个猜想呢？
对于程序员来说，当然是想编写程序来查找素数和孪生素数。当然，由于计算机位数的限制，所表示的整数范围是有限的，如果要找出更多的素数或孪生素数，需要另外编写大整数处理的相关功能。
由于篇幅限制，本书将不介绍大整数方面的功能，下面只列出一个简单的求解孪生素数的程序。在程序中，将先筛选出素数，然后在素数中再筛选出孪生素数。
执行以上程序，将得到如图2-7所示的结果。从结果中可以看到，在10000以内共有1229个素数，而孪生素数只有205对。
图2-7
在上面的程序中，常量MAXNUM定义为10000，即可求出10000以内的素数，如果将MAXNUM定义为更大的常量值，则可求出更多的素数和孪生素数。当然要注意，由于计算机中变量表示范围及程序栈空间大小的限制，MAXNUM定义的数据大小是有限的。
