显然,在数列的开始部分,素数是十分常见的,因为小的数没有多大可能会有因数分解。在这之后,素数越来越稀少。比如,只有一组连续3个奇素数:3,5,7。这三者的组合是独一无二的,因为每3个奇数就会出现1个3的倍数,所以这种情况再也不会发生。此外,素数出现频率减少的过程是十分松散的,还非常不规律。比如,30~40之间只有两个素数,即31和37,但刚过100就会有两个“相继的”孪生素数对,即101,103和107,109。
素数在数千年来一直深深吸引着人们[8],因为它们无穷无尽(我们在下一章会证明这个说法),在自然数中现身的方式又神出鬼没。它们性质中神秘莫测的这一面在现代密码学(cryptography)中被加以运用,来保护互联网上的机密信息。这将是第4章的话题。
素性检验:素数整除性测试
为了找出不大于某个数(比如100)的所有素数,最容易想到的方法是把所有数写下来,再寻找并画掉里面的合数。基于这一思想的标准方法叫作埃拉托斯特尼筛法[9](Sieve of Eratosthenes)。方法如下:首先圈出2并画掉列表里2的倍数(即其他偶数)。然后回到开始,圈出第一个尚未被画掉的数(即3),画掉剩下数表里它的所有倍数。重复这一过程足够多遍,剩下没有被画掉的就是素数。即便它们中一些被圈出来了,而另一些没有。例如,图1展示了对不大于60的数运用筛法的过程。