1 素数的判别与个数

如果一个大于1的自然数只能被l及它本身整除，则该数称为素数，否则称为合数。从数学史的黎明时期开始，数学家们就一直在探索自然数的奥秘。远在古希腊时代，欧几里得就证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时这种分解是唯一的，这就是所谓的算术基本定理。算术基本定理表明，素数是构造自然数的基石，正如物质的基本粒子一样。正是由于素数如此重要的地位才使得一代又一代数学家努力地探询素数的规律。首先，一个最基本的问题是素数到底有多少个?会不会在某一充分大的自然数以后就没有素数呢?

2 素数表的构造

古希腊另一位学者Eratosthenes给出了解决问题的方法，这一方法被后人称为Eratosthenes筛法。Eratosthenes筛法的基本思想是，将自然数列从2开始按顺序排列至某一整数。首先，从上述数列中划除所有2的倍数(不包括2)。在剩下的数中，除2外最小的是3。接着，从数列中划掉所有3的倍数(不包括3)。然后在剩下的数中，再划去5的倍数……。这个过程一直进行下去，则最后剩下的数就是不超过的所有素数。借用Eratosthenes筛法，经过众多学者的艰辛努力，D.N.Iehmer于1914年编织出了10 000 000以内的素数表。利用Eratosthenes筛法，请同学们手工编写100以内的素数表。据此，思考如何估计利用筛法编写10000000以内的素数表的工作量? 筛法是用乘法寻找素数。实际上，也可以用除法判别一个数是否是素数。而且，用除法的效率可能会更高。假设我们已经找到了前个素数，为了寻找下一个素数我们从开始依次检验每一个整数，看是否能被某个，整除。如果能被前面的某个素数整除，则为合数。否则即为下一个素数，实际上，为了提高算法的效率，人们不需用前面的每一个素数去试除，而只需用不超过的素数去除就可以了。

3 素数的判别公式

数十年前，象l l…1(23个1)以及的素性判别问题难倒了许多睿智的数学家。当今，数学家研究出了一套非常复杂而高深的技巧来对数的素性进行检验。寻找到的最大素数的高峰一股劲地向上无限攀升。截止到2008年，所找到的最大素数是，这是第 46个 梅森(Mersenne)素数，其十进制形式有1300万位！为了领略一下隐藏在这些高深技巧下面的数学思想，请同学们做以下实验。

对，观察被整除所得的余数。从观察结果你能得出什么结论?再取其它的整数 (如3，4，5)，观察被整除的情况。特别注意观察当为素数时的结果。能否因此确信你的结论?进一步，你所得出的结论的逆命题是否成立?由此，用你的结论能否给出判别一个数是否是素数的判别方法?

   对互质的整数及，求使得除的余数为1的最小整数。当视为素数时，观察与之间的关系，你能得到什么结论?类似地，对做进一步的观察，你能否确信你的结论?你所得出的结论的逆命题是否成立?

4生成素数的公式

虽然我们在本段给出了生成素数表的算法，但要找到大的素数确是异常的艰辛。你也许会想，要是能找到一个正好生成全部素数的公式就好了。例如，是否存在单变量整系数的多项式，它只生成素数并且生成所有的素数?更一般地，是否存在一个生成素数的多变量函数公式?如果这样的公式不存在，能否找到一个虽不能给出全部但能给出无穷多个素数(且只给出素数)的公式?实际上，早在十七、十八世纪，大数学家Fermat，Euler等就研究过这类公式。1640年Fermat在给Mersenne的信中指出，对所有的整数，永远是素数。的确，，，，，都是素数。然而，好事到此为止。1732年，大数学家Euler指出，不是素数，他并且找到了的因子分解。此后，人们分别证明了，与都是合数，并得到了它们的素因子分解。实际上有人猜测当时都是合数。由此可见，Fermat当初的猜测离真实结果相差有多远。

Fermat数与正多边形做图有紧密的联系。这一惊人的发现是伟大的德国数学家Gauss得到的。Gauss在19岁那年证明了：一个正边形可用直尺与圆规作图的充要条件是，或者，其中为不同的Fermat数。特别地，正17边形可以用直尺与圆规做出。

1772年Euler研究过用单变量的整系数多项式来生成素数，其最著名的例子是。

对，计算。它们是否都给出素数?在l0 000以内的素数中，由公式给出的素数占多少?类似地，对公式及做同样的判别。

5素数的分布

如果将素数在数轴标出来，同学们会发现素数的分布很不规则。通过以下实验做进一步的观察。

（1）用表示不超过的素数的个数，表示区间内素数的个数。试计算，，以及，，，。从计算结果看，随着整数范围的扩大，者数是越来越稀还是越来越密？选取一些更长的区间，再尝试以上同样的实验。

（2）将素数从小到大顺序排列，，…，用表示相邻素数间的间隔。计算(如＝1000，10000等)，然后将点标在平面坐标系中。你能从中观察到素数的间隔有什么规律呜?譬如，素数的间隔值有哪些?它们各重复多少次?哪些间隔值的重复次数多?最大间隔值是多少?随增大，最大间隔值是否也随之增大?

根据上述实验，你对素数的分布能做什么样的猜测?譬如，间隔差为2的素数是否有无穷多个?更一般地，间隔差为某个偶数的素数对是否有无穷多个?是否存在相邻的素数，其间隔值可以任意大?你能否证明你的这些猜测?

在二维坐标平面上标出点列， (取不同的，如1000，10 000等)，也可以用折线将点列连接起来。观察趋于无穷的趋势，将它同比较。你能得出什么结论?类似地观察点列 ，及。你能据此猜测趋于无穷的极限阶吗?

    令，，其中。试对一系列充分大的，计算，，，及。其中哪一个公式更接近?

6 用函数对素数的个数进行拟合

用函数对素数的个数进行拟合。先进行线性拟合，选取2到1000中所有的素数进行拟合，再改变拟合的多项式的次数，比较拟合效果。

      将点（, ）标在平面坐标系中,并且用折线把这些点连接起来，观察的变化趋势，然后在程序中增大的值，再观察的变化趋势，将的值与其它函数的值进行比较，看能否找出最接近的值的函数，即计算素数个数的公式，注意此时应该充分大。