素数的实验报告.doc

《素数的实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、素数理学院数学061赵欣0602012003一．实验解读素数的问题是数论里最富有魅力，最吸引人的问题，在本次实验中我们将研究讨论素数的一些相关规律及性质，在看似无规律的素数中寻找规律。要想研究素数，首先要了解素数的定义，学会用定义去判断一个数是否是素数，考虑合数与素数之间具有什么样的关联。通过一些相关结论猜测素数的无穷性并给出证明，并分别用试除法和筛法列出一定范围内的素数表，比较这两种方法的有效性。在实验过程中，我们发现素数并没有一个简明的判别公式，那么就需要通过实验构造出素数的判别公式。在研究用整系数多项式来生成素数时，最关键的是恰当地选择多项式的次数与变量的个数。

2、最后，通过研究一定范围内的素数个数随整数增加而变化的关系，得出素数的分布特征。观察它的变化关系，并用函数将素数的分布表示出来。二．实验方案1.素数的判别与个数在大于1的自然数中，只能被1和它本身整除的数称为素数。在素数研究中，一个最基本的问题是素数到底有多少个，是否是无穷的。规定Nn=p1p2......pn+1，当n=1,...,20时判断Nn是否是素数，如果不是，那么Nn能不能表示成几个素因子相乘的形式。调大n至25，观察并得出结论。再将n调至30，35……，结论是否发生了变化。根据以上的结果，猜测素数是否有无穷多个，并给出相关的证明。2素数表的构造给出一个范围，

3、用Eratosthenes筛法和试除法列出该范围内所有的素数，它们的原理为：Eratosthenes筛法的基本原理，将自然数列从2开始按顺序排列至某一整数N，首先，从上述数列中划除所有2的倍数（不包括2），在剩下的数中，除2外最小的是3.接着，从数列中划除所有3的倍数（不包括3），然后在剩下的数中，再划去5的倍数······这个过程一直进行下去，则最后剩下的数就是不超过N的所有素数。试除法：假设我们已经知道前n个素数p1=2,p2=3,...,pn，为找下个素数，我们从pn+2开始依次检验每一个整数N，看是否能被某一个pi(i=1,2,...,n)整除，若N能被前面的

4、某个素数整除，则N为合数，否则N即为下一个素数pn+1。为了提高效率我们只需要用不超过N^(1/2)的素数去除就可以了。在两者都能实现我们实验目标德尔情况下比较Eratosthenes筛法和试除法这两种方法的有效性。比较同样是列出1000以内的素数，看哪种方法用的时间比较少。将范围调大，用这两种方法列出10000，100000……以内的素数，再比较它们所用的时间，以此来确定这两种方法的有效性。3素数的判别公式对n=2,3,…,100中不同的数,观察m^(n-1)被n整除所得的余数。将m的值固定，变化n的值为2，3，……100取m=2，观察2^(n-1)被n整除所得的余

5、数取m=3，观察3^(n-1)被n整除所得的余数取m=4，观察4^(n-1)被n整除所得的余数………如果我们固定的是n的取值，变化m的值，那么我们得出的结果又会怎样？取n=2，m=2,3,4,……，20，观察m^(2-1)被2整除所得的余数取n=3,m=2,3,……，20，观察m^(3-1)被3整除所得的余数取n=5,m=2,3,……，20，观察m^(5-1)被5整除所得的余数得出一般性结论，并加以证明。Mersenne数的素性判别：形如2^n-1的数称为Mersenne数，通过Mersenne数我们可以研究数论中的相关性质。观察并考虑Mersenne数与n的关系，得

6、出一般性的结论，加以证明。4.生成素数的公式Fermat数：我们把形如+1表示出来的数称为Fermat数。Fermat数是否都是素数？在程序中增大n的值，很容易知道当n变大到一个特定的值时，Fermat数不再是素数。既然Fermat数不能作为素数的生成公式，那么能不能寻求一个整系数单变量多项式，使得它能生出所有的素数。首先考虑一次函数，显然是不行的。再考虑二次多项式，如：f(n)=+n+41，f(n)=-79n+1061，f(n)=6+6n+31，观察是否无论n如何变化，f(n)都是素数。若不是，再改变多项式的次数，令f(n)=，f(n)=，f(n)=令变量n的次数不

7、断升高，观察得出的结果有什么不同。若单变量整系数多项式不能生成所有的素数，那么多变量整系数多项式呢？考虑两个变量的函数，f(n,m)=n+m+4，将两个变量的多项式的次数变为二次，令f(n,m)=，再改变为三次的，令f(n,m)=，逐步升高多项式的次数，令f(n,m)=。判断以上的f(n,m)是否生成的均是素数，它们之间有什么规律？若还是无法找出这样的两个变量整系数多项式，再改变多项式的变量的个数和次数。得出概括性的结论。5.素数的分布在上面的实验中我们已经知道了素数是无穷多个的，而且素数的生成公式并不是很明了，但是它的分布会不会具有什么样的规律呢？