3.2 筛选素数
毕达哥拉斯学派的人还观察到一个现象，那就是有些数字没有办法表示成非平凡的矩形形状（nontrivial rectangular shape），也就是说，没有办法用两个边都大于1的矩形来表示。这种数叫做素数（prime number），它们不能够用比其更小且大于1的数之间的乘积来表示：
2, 3, 5, 7, 11, 13,…
（古希腊人所说的数都是指整数。）某些与素数有关的特征最早是由欧几里得观察到的。尽管大家通常都会把他与几何学联系起来，但是《几何原本》中有很多卷内容其实是在讲数论。他所得到的其中一项结论就是下面这条定理：
定理3.1（《几何原本》第7卷第32号命题） 任何数要么是素数，要么可以为某个素数所整除。
该定理的证明过程采用了一项技巧，它通过无穷递降法（infinite descent）推导出一种不可能存在的情形。我们可以将此过程陈述如下：
证明 考虑A这个数。如果它是素数，那么就得证。如果它是合数（composite，也就是非素数（nonprime）），那么必定能够为某个更小的数B所整除。如果B是素数，那么得证（由于A可以为B所整除，而B又是素数，因此A就可以为该素数所整除）。如果B是合数，那么必定能够为某个更小的数C所整除，依此类推，我们最后必然能够找到一个可以整除A的素数，假如找不到这样的素数，那么就会像欧几里得在证明同卷第31号命题时所说的那样：得到一个无穷数列（infinite sequence of numbers），其中的每个数都可以整除A，而且后一个数要比前一个数小。然而这样一种数列是不可能存在的。□
欧几里得的证明过程依赖于一项原则，那就是：由降序的自然数所形成的数列必定会终结。此原则与我们将要在第9章提到的自然数归纳公理（induction axiom of natural numbers）是等价的。
-
- *
欧氏所得出的另一条结论，是说素数的个数无限多，有人认为这是最美的数学定理：
- *
定理3.2（《几何原本》第9卷第20号命题） 对于由素数所构成的任何一个数列{p1,…, pn}来说，总有一个素数p不在该数列中。
证明 考虑下面这个数：
其中的pi是指数列中的第i个素数。根据q的构造方式可知，它不可能为任何一个pi所整除。因此，q要么本身就是素数，要么则可以为不在数列中的其他某个素数所整除。如果是前一种情况，那么q必然不在这个数列中；如果是后一种情况，那么根据该数列的定义可知，能够整除q的那个素数也不在这个数列中。因此，素数的个数是无限多的。
有一种广为人知的素数搜寻方法，叫做埃拉托斯特尼筛法（Sieve of Eratosthenes）。埃拉托斯特尼是公元3世纪的希腊数学家，他的一项壮举是相当精确地测量了地球的周长。这种素数搜寻算法的原理是将数字放在筛子里进行筛选，把其中的非素数筛掉，使得素数能够留在筛子里面。执行算法时，要把所有的候选数字写下来，然后将其中已知的非素数划掉（这些数都是已经找到的那些素数的倍数），剩下来的数就是素数。今天在演示该算法的时候，会把从2到某个给定值之间的所有数字全部写下来，但由于埃拉托斯特尼当时已经知道2之外的偶数都不是素数，因此他并没有把这些数包含在内。
下面我们也按照埃氏的习惯，将偶数排除在外，也就是说，只寻找大于2的那些素数。我们把从3开始直到给定值（该值记为m）之间的每一个候选数字，都放在筛子里面。比方说，如果要寻找3到53（此时m = 53）之间的素数，那么筛子里面一开始会有这些数字：
反复执行这个筛选过程，直到把小于等于的倍数全都划掉为止，其中的m是指候选数字里面最大的那个数。
对于本例来说，由于m = 53，因此只需要执行到7的倍数这一轮就可以停止了。还没有划掉的数字全都是素数：
在用程序代码实现该算法之前，我们先来观察它的几项特征。在筛选过程进行到一半的时候（比方说，在正要划掉5的倍数时），我们给候选数字添加一些信息，也就是把每个数字在数列中的序号（index）或者说位置标在该数上方。
大家可以看到，在考虑5的倍数时，我们所划掉的25和35这两个数字，其距离恰好是5，这个间隔距离就叫做步长（step size）。如果改用另外一种说法，那就是：在某一轮筛选过程中所划掉的这两个候选数字，其序号之间的差距等于本轮开头所用的那个素数。此外，由于候选数列中只包含奇数，因此，划掉的这两个数值其数量差距是序号差距的2倍。所以我们可以说，某一轮筛选过程中所划掉的这两个候选数字（例如25和35）其数量差距是步长的2倍，或者说是本轮开头所用的那个素数的2倍。刚才我们是以5为例来进行说明的，对于其他数字来说，这个规律同样成立。
最后，我们还观察到另外一个现象，那就是：每一轮筛选时，第一个划掉的数字总是当前这一轮所用的那个素数的平方。例如在考虑5的倍数时，第一个划掉的数字必然是25，因为尽管两者之间还有一些数字也是5的倍数，但我们早前在考虑其他素数时，已经把那些数划掉了。