2.1　素数搜索

在进行素数搜索前，有必要清楚素数有多少个，是有限个还是无穷多个。

对于这一问题，两千多年前的欧几里得给出了以下明确的回答。

【命题】　素数有无穷多个。

【证明】　下面用反证法证明。

假设素数只有有限的n个，不妨设为p1，p2，…，pn。

考察整数p＝p1p2…pn＋1，无非以下两种可能。

（1）整数p是合数。

如果整数p是合数，则p能被某一素数q整除。

若素数q是n个素数p1，p2，…，pn中的一个，则p1p2…pn能被q整除，又p＝p1p2…pn＋1能被q整除，因而1能被q整除，这显然是不可能的。

若素数q是n个素数p1，p2，…，pn以外的一个，则与假设矛盾。

（2）整数p是素数。

显然素数p＝p1p2…pn＋1大于p1，p2，…，pn中的任何一个，是一个新的素数，与假设矛盾。

因而得证素数有无穷多个。

探讨素数，首先必须清楚哪些正整数是素数，哪些正整数不是素数。

搜索素数的常用方法有试商判别法与厄拉多塞筛法两种。这两种方法各具特色，本节具体探讨应用这两种方法搜索素数。

2.1.1　试商判别法

试商判别法是依据素数的定义来实施的。

试应用试商判别法求出指定n位所有素数，并统计n位素数的个数。

1. 设计要点

应用试商判别法来判别奇数k（只有唯一偶素数2，不作试商判别）是不是素数，只要逐一用奇数j（取3，5，…，直至）去试商。

若存在某个j能整除k，说明k能被1与k本身以外的整数j整除，k不是素数。

若上述范围内的所有奇数j都不能整除k，则k为素数。

注意：有些程序把试商奇数j的取值上限定为k/2或k-1，这也是可行的，但并不是可取的，这样无疑会增加许多试商的无效循环。

理论上说，如果k存在一个大于且小于k的因数，则必存在一个与之对应的小于且大于1的因数，因而从判别功能来说，取到已足够了。

判别j整除k，在C程序中常用表达式k%j＝＝0来实现。

2. 应用试商判别法求n位素数程序设计
3. 程序运行示例与说明
     请指定位数n(n>1):4
     1009　1013　1019　1021　1031　1033　1039　1049　1051　1061
     1063　1069　1087　1091　1093　1097　1103　1109　1117　1123
     ……
     9883　9887　9901　9907　9923　9929　9931　9941　9949　9967
     9973
     共1061个4位素数。

从搜索结果可以看出，最小的4位素数为1009，最大的4位素数为9973，共有1061个4位素数。

试商判别法简单直观，设计容易实现，因此常为程序设计者所采用。

2.1.2　厄拉多塞筛法

搜索素数，除了试商判别法之外，还有历史更为悠久、效率更高的厄拉多塞筛法。本节简单介绍厄拉多塞筛法及其在搜索素数上的应用。

1. 厄拉多塞筛法简介

求素数的筛法是公元前3世纪的厄拉多塞（Eratosthenes）提出来的：对于一个整数k，只要知道不超过的所有素数p，划去所有p的倍数2p，3p，…，剩下的整数就是不超过k的全部素数。

【问题】　试应用厄拉多塞筛法求区间[100，200]中的素数。

【探求】　分以下4步求解。

（1）首先求出不超过的所有奇素数3，5，7，11，13，共5个。

（2）列出区间[100，200]中的所有奇数，共50个。

（3）在所列50个奇数中，分别划去3的倍数、5的倍数、7的倍数、11的倍数与13的倍数（见图2-1，分别以不同划符标记）。

图2-1　应用筛法求素数划去操作图

（4）剩下没有划去的整数即为素数。

通过以上划去操作实施筛选，剩下以下整数为素数。

即得区间[100，200]共有以上21个素数。

2. 应用筛法搜索素数设计要点

为扩大搜索范围，相应变量设置为double型。

（1）实施划去操作。

应用筛法求素数，为了方便实施划去操作，应设置数组。

每一数组元素对应一个待判别的奇数，并赋初值0。

如果该奇数为p的倍数，则应划去，于是对应元素加一个划去标记，例如给该元素赋一个负数-1。最后，打印元素值不是-1（即没有划去）的元素对应的奇数即所求素数。

在指定区间[c，d]（约定c为奇数）上所有奇数表示为j＝c＋2k（k＝0，1，…，e，这里e＝（d-c）/2）。于是k＝（j-c）/2是奇数j在数组中的序号（下标）。如果j为奇数的倍数，则对应数组元素作划去标记，即a[（j-c）/2]＝-1。

（2）放宽划去对象。

在实际应用筛法的搜索过程中，p通常不一定取不超过的素数，而是适当放宽取不超过的奇数（从3开始）。这样做尽管多了一些重复划去操作，但省去了求不超过的素数这一环节，程序实现要简便些。

根据c与奇数i，确定g＝2∗（floor（c/（2∗i）））＋1，使得g∗i接近区间下限c，从而使划去的gi，（g＋2）i，…在[c，d]中，这样可减少无效操作，提高对大区间的筛选效率。

最后，凡数组元素a[k]≠-1，则输出对应的奇数j＝c＋2∗k即为素数，并应用变量n统计该区间的素数个数。

3. 筛法求素数程序设计
4. 程序运行示例与说明
     请输入区间[c,d]的c,d(c>2):1480028120,1480028220
     1480028129　1480028141　1480028153　1480028159
     1480028171　1480028183　1480028189　1480028201
     1480028213
     共9个素数。

这9个连续素数（中间没有其他素数）在第10章中将会构建一个3阶素数幻方。

筛法在较大区间的搜索与较大整数的判别上效率比试商判别法更高一些，但设计上较难把握。

运行程序，输入区间[10 000，99 999]，快捷输出99 991等共8363个5位素数。

上一章目录下一章