如何有效寻找素数

埃拉托色尼

取一个正整数x ，如何才能找出不超过x 的所有素数呢？有一种方法叫作埃拉托色尼筛法，其历史可以上溯到古希腊时期。

埃拉托色尼筛法的步骤如下：第一步，列出从2到x 的所有整数，保留2，划去所有2的倍数。第二步，在剩余的数列中，紧跟着2的素数是3；保留3，划去所有3的倍数。第三步，在剩余的数列中，紧跟着3的素数是5；保留5，划去所有5的倍数。

埃拉托色尼筛法

如此下去，最后一步是，在倒数第二步的剩余数列中，保留最接近且不超过根号x的那个素数，划去这个素数的所有倍数。

这样，剩下的数列就是不超过x 的所有素数。

以上做法是基于这样的事实：若a 不是素数，则a 一定有不大于 根号a 的因子。

用埃拉托色尼筛法可以比较方便地编制素数表。要是碰到一个不很大的正整数a （比如不超过10000），手头刚好没有素数表可查，如何快速地判定它是否是素数呢？事实上，只要拿不大于根号a 的一切素数去试除a 就可以了。

【微博士】 自然中的筛法

蝉是一种有趣的昆虫。当它还是幼虫的时候，在地下成长很多年，然后破土而出、交配、产卵。科学家发现，许多蝉在地下蛰伏的年数是素数，如13年、17年，为什么呢？原来，这是为了生存、繁衍安全的需要，选择素数使它避开很多天敌。比如，17年周期蝉，可能会遇到1年周期和17年周期的天敌（包括同类）；而18年周期蝉就可能会遇到1、2、3、6、9、18年周期的天敌，显然处境危险多了。这是巧妙的解释！但是，难道蝉也懂数论吗？当然不可能！唯一的解释是，这是大自然进化的结果。可以想象，本来很可能有各种周期的蝉，经过亿万年的漫长岁月，那些合数周期的蝉由于遇到天敌过多，慢慢地就退出了历史舞台。自然选择无处不在，而在蝉的身上，自然选择看上去就像是筛法——自然的筛法。

哥德巴赫猜想是要证明“1+1=2”吗

1978年，作家徐迟在《人民文学》发表了报告文学《哥德巴赫猜想》，讲述了中国数学家陈景润在哥德巴赫猜想研究中的杰出贡献，由此很多人知道了哥德巴赫猜想，并认为哥德巴赫猜想就是要证明“1+1=2”。哥德巴赫猜想果真是要证明“1+1=2”吗？

早在1742年，德国人哥德巴赫写信给大数学家欧拉，提出了两个猜想：（1）任何一个大于2的偶数都是两个素数之和；（2）任何一个大于5的奇数都是三个素数之和。欧拉表示他相信哥德巴赫的猜想是对的，但他不能加以证明。很容易证明（2）是（1）的推论。所以，第一个猜想是最基本的，由于素数只有一个因子，所以通常将猜想（1）表示为（1+1）。（1+1）其实是哥德巴赫猜想的一种表示，而不是要证明“1+1=2”，“1+1=2”是不需要证明的。

1+1=2是无需证明的

哥德巴赫的手稿

哥德巴赫猜想吸引了世界上很多著名数学家的兴趣，并在证明上取得了很好的成绩。

1922年英国数学家哈代与李特尔伍德提出了“圆法”。1937年，苏联数学家伊万·马特维耶维奇·维诺格拉多夫就应用圆法，结合他自己创造的方法，证明了每个充分大的奇数都是三个素数之和，基本上证明了哥德巴赫猜想的第二题。这样，哥德巴赫猜想就主要指第一题了。

世界上的数学家对这个难题下了不少的工夫。1920年，挪威数学家布朗改进了古老的“筛法”，证明了每个充分大的偶数都是两个素因子个数不超过9的正整数之和，即（9+9）。德国数学家拉代马哈在1924年证明了（7+7）。英国数学家埃斯特曼于1932年证明了（6+6）。苏联数学家布赫夕塔布于1938年和1940年分别证明了（5+5）与（4+4）。这好像运动员不断地刷新着世界纪录。

1956年，中国数学家王元证明了（3+4），同一年，苏联数学家阿·维诺格拉多夫证明了（3+3）。1957年王元证明了（2+3）。这些结果的缺点，在于两个相加的数中还没有一个可以肯定为素数的。

到了1962年，中国数学家潘承洞与苏联数学家巴尔巴恩各自独立证明了（1+5）。1963年，潘承洞、王元和巴尔巴恩都证明了（1+4）。1965年，阿·维诺格拉多夫、布赫夕塔布与意大利数学家邦别里证明了（1+3）。中国数学家陈景润在对筛法作了新的重要改进之后，于1966年证明了（1+2），取得了迄今世界上关于哥德巴赫猜想（1）这个难题的最好成绩。他证明了：任何一个充分大的偶数，都可以表示为两个数之和，其中一个是素数，另一个或者是素数，或者是两个素数的乘积。世界上称这个定理为“陈氏定理”。这个定理受到了世界数学界的重视，不少数学家致力于简化这个定理的证明。目前世界上已有五个简化证明，最简单的简化证明是由中国数学家王元、丁夏畦和潘承洞共同作出的。

哥德巴赫猜想的证明还没有结束，还需要作最后的冲刺。经过了这几十年来世界各国数学家的研究，我们可以看出，哥德巴赫猜想也像其他经典问题一样，它的一切成就都是在前人成就的基础上，通过迂回的道路而得到的。如果连数论基础知识都没有认识，前人的成果也没有摸过，而凭着热情来企图证明（1+1），那只能是浪费时间和导致错误的结果。数学是一门很严谨的学问，不能草率马虎，既要有敢于创新的精神，更要有严谨的科学态度，这是许许多多数学家成功的要诀。

【微博士】 猜想与定理

“在数学研究中，往往根据一些感性认识，小心地提出“猜想”，然后再通过严格的数学推导来论证。被证明了的猜想，就变成了“定理”，但也有不少猜想被否定了。

【微博士】 陈氏定理

1966年，中国数学家陈景润发表了一个数论定理——陈氏定理。这个定理证明了任何一个足够大的偶数都可以表示成两个素数的和，或是一个素数和一个半素数（只有两个素因子的合数）的和。简单地称为（1+2）。陈景润的论文是这样表示这个定理的：对于任何一个大偶数N，总可以找到奇素数P '、P "，或者P 1 、P 2 、P 3 ，使得下列两式至少一式成立：

N =P '+P ”

N =P 1 +P 2 ×P 3

当然并不排除两式同时成立的情形，如62=43+19，62=7+5×11。