探索数学实验报告 素数.doc

实 验 报 告实验名称： 素数班 级：统计 111姓 名：饶红梅学 号：1102092005探索实验一 素数实验报告一、实验背景与实验目的德国数学家高斯说过，数学是科学的女王，而数论则是数学的女王在数论这一充满了趣味而布满荆棘的领域中，有关素数的问题(如著名的Goldbach 猜想)始终是最富有魅力最吸引人的研究问题本实验将探索素数的规律及其相关的某些有趣问题：（1）素数表的构造；（2）素数的判别；（3）最大的素数；（4）构造生成素数的公式；（5）素数的分布二．实验计划.1.素数的判别与个数在大于 1 的自然数中，只能被 1 和它本身整除的数称为素数规定 Nn=p1p2......pn+1，当 n=1,...,20 时判断 Nn 是否是素数，如果不是，那么 Nn 能不能表示成几个素因子相乘的形式 改变 n 的取值范围，观察得出结论根据以上的结果，猜测素数是否有无穷多个，并给出相关的证明2. 素数表的构造用 Eratosthenes 筛法和试除法列出 1000 内所有的素数，比较哪种方法所用的时间比较少它们的原理为：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 能被前面的某个素数整除，则N 为合数，否则 N 即为下一个素数 pn+1为了提高效率我们只需要用不超过N^(1/2)的素数去除就可以了. 3.素数的判别公式对 n=2 ,3 ,…, 100 中不同的数,观察 m ^( n - 1)被 n 整除所得的余数将 m 的值固定，变化 n 的值为 2，3，……100取 m=2，观察 2 ^( n - 1)被 n 整除所得的余数取 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 的关系，得出一般性的结论，4.生成素数的公式Fermat 数：我们把形如 +1 表示出来的数称为 Fermat 数FermatnF2数是否都是素数？在程序中增大 n 的值，很容易知道当 n 变大到一个特定的值时，Fermat 数不再是素数既然 Fermat 数不能作为素数的生成公式，那么能不能寻求一个整系数单变量多项式，使得它能生出所有的素数首先考虑一次函数，显然是不行的再考虑二次多项式，如：f(n)= +n+41，f(n)= -79n+1061，f(n)=6 +6n+31，观察是否无论 n 如何变化，2n2n2nf(n)都是素数若不是，再改变多项式的次数，观察得出的结果有什么不同若单变量整系数多项式不能生成所有的素数，那么多变量整系数多项式呢？判断以上的 f(n ,m)是否生成的均是素数，它们之间有什么规律？5.素数的分布在上面的实验中我们已经知道了素数是无穷多个的，而且素数的生成公式并不是很明了，但是它的分布会不会具有什么样的规律呢？实验中，用 表示不超过 n 的素数的个数， 表示区间 [m,n] 内)(n ),(nm素数的个数，再计算 ﹑ ﹑ 以及 ﹑10)()10(201﹑ ﹑ 。

从计算结果看，随着范围)10,(,( ,的扩大，素数是越来越稀还是越来越密？进一步，选取一些更长的区间，做同样的实验将这些点画在图中，从图中能更清晰的看出素数的分布情况换一个角度考虑，从两个相邻素数间距的大小同样也可以看出素数的分布，这时我们还可以发现一些更有趣的规律先求出 1000 以内的所有相邻素数的间距，并将点以（ ， ）的形式画在直角坐标系中，观察图像的特点；增大 nnpd的值，再在另一个图中画出，从这些点的分布可以看出素数的间隔值的某些特征，以及它们的重复次数的多少，我们还发现：在增大 N 的值的同时，图中的点也会随之变高，也就是说最大间隔值在变化 6.用函数对素数的个数进行拟合用函数对素数的个数进行拟合先进行线性拟合，选取 2 到 1000 中所有的素数进行拟合，再改变拟合的多项式的次数，比较拟合效果将点（n, ）标在平面坐标系中,并且用折线把这些点连接起来，观察)(n的变化趋势，然后在程序中增大 N 的值，再观察 的变化趋势，将)(n )(n的值与其它函数的值进行比较，看能否找出最接近 的值的函数，即计算素数个数的公式，注意此时 n 应该充分大三、实验过程与结果1 素数的判别与个数运行 Mathematica如下程序：NumP[n_Integer]:=Module[{i,Num},Num=Product[Prime[i],{i,1,n}]+1;Print[Num];Print[PrimeQ[ Num]];Print[FactorInteger[Num]]]Do[NumP[n],{n,1,20}]运行结果为;1）n=20 时3True{{3,1}}7True{{7,1}}31True{{31,1}}211True {{211,1}}2311True{{2311,1}}30031False{{59,1},{509,1}}510511False{{19,1},{97,1},{277,1}}9699691False{{347,1},{27953,1}}223092871False{{317,1},{703763,1}}6469693231False{{331,1},{571,1},{34231,1}}200560490131True{{200560490131,1}}7420738134811False{{181,1},{60611,1},{676421,1}}304250263527211False{{61,1},{450451,1},{11072701,1}}13082761331670031False{{167,1},{78339888213593,1}}614889782588491411False{{953,1},{46727,1},{13808181181,1}}32589158477190044731False{{73,1},{139,1},{173,1},{18564761860301,1}}1922760350154212639071False{{277,1},{3467,1},{105229,1},{19026377261,1}}117288381359406970983271False{{223,1},{525956867082542470777,1}}7858321551080267055879091 False{{54730729297,1},{143581524529603,1}}557940830126698960967415391False{{1063,1},{303049,1},{598841,1},{2892214489673,1}}2）n=25 时：557940830126698960967415391False{{1063,1},{303049,1},{598841,1},{2892214489673,1}}40729680599249024150621323471False{{2521,1},{16156160491570418147806951,1}}3217644767340672907899084554131False{{22093,1},{1503181961,1},{96888414202798247,1}}267064515689275851355624017992791False{{265739,1},{1004988035964897329167431269,1}}23768741896345550770650537601358311False{{131,1},{1039,1},{2719,1},{64225891884294373371806141,1}}2305567963945518424753102147331756071False{{2336993,1},{13848803,1},{71237436024091007473549,1}}3)N=30 2305567963945518424753102147331756071False{{2336993,1},{13848803,1},{71237436024091007473549,1}}232862364358497360900063316880507363071False{{960703,1},{242387464553038099079594127301057,1}}23984823528925228172706521638692258396211False{{2297,1},{9700398839,1},{179365737007,1},{6001315443334531,1}}2566376117594999414479597815340071648394471False{{149,1},{13203797,1},{30501264491063137,1},{42767843651083711,1}}279734996817854936178276161872067809674997231False{{334507,1},{1290433,1},{648046444234299714623177554034701,1}}31610054640417607788145206291543662493274686991False{{5122427,1},{2025436786007,1},{3046707595069540247157055819,1}}4)N=3531610054640417607788145206291543662493274686991False{{5122427,1},{2025436786007,1},{3046707595069540247157055819,1}}4014476939333036189094441199026045136645885247731False{{1543,1},{49999,1},{552001,1},{57900988201093,1},{1628080529999073967231,1}}525896479052627740771371797072411912900610967452631False{{1951,1},{22993,1},{11723231859473014144932345466415143728266617,1}}72047817630210000485677936198920432067383702541010311False{{881,1},{1657,1},{32633677,1},{160823938621,1}。