数学实验实验报告-素数的分布

素数的分布

一、 实验目的

只有1和它本身两个自然数作为因数的大于1的整数称为素数。本实验将通过计算机发现素数的规律及素数的一些有趣现象和性质，具体地我将研究有关素数的下列问题：

◆ 素数分布的几何与数值观察 ◆ 利用数学软件求素数 ◆ 素数分布的规律性

通过此次试验对素数的分布进行深入研究，窥探数学的奥秘。

二、 实验环境：Mathematica8.0

三、 实验内容和步骤及其对得到结果的分析

实验1：素数分布的几何与数值观察

如果一个大于1的自然数只能被1及它本身整除，则该数称为素数。否则被称为合数。从数学史的黎明时期开始，数学家一直在探索自然数的奥秘，远在古希腊时代，欧几里德就证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时这种分解时唯一的，这就是算术基本定理。算术基本定理表明，素数是构造自然数的基石，正如物质的基本粒子一样。

首先，我们不禁要问：素数到底有多少个？会不会在某一充分大的自然数以后就没有素数了呢？答案是否定的，欧几里德时代已经证明了这一结论。他使用的简洁而优美的论证方法至今仍不失为数学推理的光辉典范。假设素数只有有限个，按从小到到达的顺序排列为p1,p2?,pn。令N?p1p2?pn?1，则N不被

pi,i?1,2,?,n 中任何一个整除。因而，N 要么是素数，要么有比pn大的素因子，这与pn为最大素数相矛盾。 程序1：素数分布的几何

用?(x)表示不超过x的素数，画出（n，π（x）），n=1，2，…，m的点阵图，观察素数的分布。 程序代码如下：

运行程序1，得到下图

12001000800600400200200040006000800010000 从图可以看到，素数应该有无穷多个，且随着n的增大，π（n）是增大的。

实验2：利用数学软件求素数

程序2：直接利用Mathematica8.0求出素数

程序代码如下：

得到如下结果：

…

程序3：利用Eratosthenes筛法，求10000以内的所有素数：

古希腊有一位学者Eratosthenes给出了解决这一问题的方法，这一方法被后人称为Eratosthenes筛法。

Eratosthenes筛法的基本思想是，将自然数从2开始按顺序排列至某一整数N。首先，从上述数列中划去所有2的倍数（不包含2）。在剩下的数中，除2

外的最小的是3，接着，从数列中划掉所有3的倍数（不包含3）。然后在剩下的数中，再划去5的倍数……，这个过程一直继续下去，则最后剩下的数就是不超过N的所有素数。借用Eratosthenes筛法，经过众学者的艰辛努力，D。N。Lamer于1914年编织出了10000000以内的素数表。

利用Eratosthenes筛法，手工编写100以内的素数表：

2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、69、71、73、79、83、87、89、97

筛法是利用乘法寻找素数。实际上，也可以利用除法判别一个数是否是素数。而且，用除法的效率可能更高。假设我们已经找到了前n个素数为了寻找下一个素数我们从pn?2开始依次检验每一个整数p1?2,p2?3,?,pn，

N，看N是否能被某个pi,i?1,2,?,n整除。如果N能被前面的某个数整除，则N为合数。否则N即为下一个素数pn?1。实际上，为了提高算法的效率，我们不需用前面的每一个素数去试除N，而只需用不超过N的素数去除就可以了。

程序代码如下：

得到的结果如下：

……

实验4：素数分布的规律性

从上述结果我们可以看出素数的出现是非常无规则的。细致的观察甚至还发现，相邻两个素数可以相距很远。素数的分布的真的没有什么规律性吗？下面我们来计算一下

??x?x的值看看。

程序4：对

??x?x的值进行分析

程序代码如下：

运行程序，得到数表t3，t4的结果分别为

它们分别对应

与

??x?x与lnx的值，可以看出这两个值比较接近，这意味着?(x)xx比较逼近，这就是说，是?(x)的一个渐进估计。 lnxlnx四、 实验结论

素数的分布有规律可循，当x无限增大时，

?(x)x/ln(x)无限向1接近（?(x)表示不超

过x的素数）。