探索数学实验报告 素数

1、实 验 报 告实验名称： 素数班 级：统计111 姓 名：饶红梅 学 号：1102092005探索实验一 素数实验报告一、实验背景与实验目的德国数学家高斯说过，数学是科学的女王，而数论则是数学的女王。在数论这一充满了趣味而布满荆棘的领域中，有关素数的问题(如著名的goldbach猜想)始终是最富有魅力最吸引人的研究问题。本实验将探索素数的规律及其相关的某些有趣问题：（1）素数表的构造；（2）素数的判别；（3）最大的素数；（4）构造生成素数的公式；（5）素数的分布。二实验计划.1.素数的判别与个数在大于1的自然数中，只能被1和它本身整除的数称为素数。规定nn=p1p2.pn+1，当n=1,.,2

2、0时判断nn是否是素数，如果不是，那么nn能不能表示成几个素因子相乘的形式。 改变n的取值范围，观察得出结论。 根据以上的结果，猜测素数是否有无穷多个，并给出相关的证明。2. 素数表的构造用eratosthenes筛法和试除法列出1000内所有的素数，比较哪种方法所用的时间比较少。它们的原理为： eratosthenes筛法的基本原理，将自然数列从2开始按顺序排列至某一整数n，首先，从上述数列中划除所有2的倍数（不包括2），在剩下的数中，除2外最小的是3.接着，从数列中划除所有3的倍数（不包括3），然后在剩下的数中，再划去5的倍数这个过程一直进行下去，则最后剩下的数就是不超过n的所有素数。 试

3、除法的基本原理：假设我们已经知道前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整除所得的

4、余数 如果我们固定的是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数的素性判别：形如2n-1的数称为mersenne数，通过mersenne数我们可以研究数论中的相关性质。观察并考虑mersenne数与n的关系，得出一般性的结论，4.生成素数的公式fermat数：我们把形如+1表示出来的数称为fermat数。fermat数是否都是素数？在程

5、序中增大n的值，很容易知道当n变大到一个特定的值时，fermat数不再是素数。 既然fermat数不能作为素数的生成公式，那么能不能寻求一个整系数单变量多项式，使得它能生出所有的素数。首先考虑一次函数，显然是不行的。再考虑二次多项式，如：f(n)=+n+41，f(n)=-79n+1061，f(n)=6+6n+31，观察是否无论n如何变化，f(n)都是素数。若不是，再改变多项式的次数，观察得出的结果有什么不同。 若单变量整系数多项式不能生成所有的素数，那么多变量整系数多项式呢？ 判断以上的f(n ,m)是否生成的均是素数，它们之间有什么规律？5.素数的分布在上面的实验中我们已经知道了素数是无穷多

6、个的，而且素数的生成公式并不是很明了，但是它的分布会不会具有什么样的规律呢？ 实验中，用表示不超过n 的素数的个数，表示区间 m,n 内素数的个数，再计算以及。从计算结果看，随着范围的扩大，素数是越来越稀还是越来越密？进一步，选取一些更长的区间，做同样的实验。将这些点画在图中，从图中能更清晰的看出素数的分布情况。换一个角度考虑，从两个相邻素数间距的大小同样也可以看出素数的分布，这时我们还可以发现一些更有趣的规律。先求出1000以内的所有相邻素数的间距，并将点以（，）的形式画在直角坐标系中，观察图像的特点；增大n的值，再在另一个图中画出，从这些点的分布可以看出素数的间隔值的某些特征，以及它们的重

7、复次数的多少，我们还发现：在增大n的值的同时，图中的点也会随之变高，也就是说最大间隔值在变化。 6.用函数对素数的个数进行拟合 用函数对素数的个数进行拟合。先进行线性拟合，选取2到1000中所有的素数进行拟合，再改变拟合的多项式的次数，比较拟合效果。 将点（n, ）标在平面坐标系中,并且用折线把这些点连接起来，观察的变化趋势，然后在程序中增大n 的值，再观察的变化趋势，将的值与其它函数的值进行比较，看能否找出最接近的值的函数，即计算素数个数的公式，注意此时n应该充分大。三、实验过程与结果1 素数的判别与个数运行mathematica如下程序： numpn_integer:= modulei,n

8、um, num=productprimei,i,1,n+1; printnum; printprimeq num; printfactorintegernum donumpn,n,1,20运行结果为;1）n=20时3 true 3,1 7 true 7,1 31 true 31,1 211 true 211,1 2311 true 2311,1 30031 false 59,1,509,1 510511 false 19,1,97,1,277,1 9699691 false 347,1,27953,1 223092871 false 317,1,703763,1 6469693231 fals

9、e 331,1,571,1,34231,1 200560490131 true 200560490131,1 7420738134811 false 181,1,60611,1,676421,1 304250263527211 false 61,1,450451,1,11072701,1 13082761331670031 false 167,1,78339888213593,1 614889782588491411 false 953,1,46727,11 32589158477190044731 false 73,1,139,1,173,1/p>

10、301,1 1922760350154212639071 false 277,1,3467,1,105229,1,19026377261,1 117288381359406970983271 false 223,1,525956867082542470777,1 7858321551080267055879091 false 54730729297,1,143581524529603,1 557940830126698960967415391 false 1063,1,303049,1,598841,1,2892214489673,12）n=25时：5579408301266989609674

11、15391 false 1063,1,303049,1,598841,1,2892214489673,1 40729680599249024150621323471 false 2521,1,16156160491570418147806951,1 3217644767340672907899084554131 false 22093,1,1503181961,1,96888414202798247,1 267064515689275851355624017992791 false 265739,1,1004988035964897329167431269,1 2376874189634555

12、0770650537601358311 false 131,1,1039,1,2719,1,64225891884294373371806141,1 2305567963945518424753102147331756071 false 2336993,1,13848803,1,71237436024091007473549,13)n=30 2305567963945518424753102147331756071 false 2336993,1,13848803,1,71237436024091007473549,1 2328623643584973609000633168805073630

13、71 false 960703,1,242387464553038099079594127301057,1 23984823528925228172706521638692258396211 false 2297,1,9700398839,1,179365737007,1,6001315443334531,1 2566376117594999414479597815340071648394471 false 149,1,13203797,1,30501264491063137,1,42767843651083711,1 2797349968178549361782761618720678096

14、74997231 false 334507,1,1290433,1,648046444234299714623177554034701,1 31610054640417607788145206291543662493274686991 false 5122427,1,2025436786007,1,3046707595069540247157055819,14)n=3531610054640417607788145206291543662493274686991 false 5122427,1,2025436786007,1,3046707595069540247157055819,1 401

15、4476939333036189094441199026045136645885247731 false 1543,1,49999,1,552001,1,57900988201093,1,1628080529999073967231,1 525896479052627740771371797072411912900610967452631 false 1951,1,22993,1,11723231859473014144932345466415143728266617,1 72047817630210000485677936198920432067383702541010311 false 8

16、81,1,1657,1,32633677,1,160823938621,1,5330099340103,1,1764291759303233,1 10014646650599190067509233131649940057366334653200433091 false 678279959005528882498681487,1,14764768614544245139224580493,1 1492182350939279320058875736615841068547583863326864530411 false 87549524399,1,65018161573521013453,1,

17、262140076844134219184937113,15)n=401492182350939279320058875736615841068547583863326864530411 false 87549524399,1,65018161573521013453,1,262140076844134219184937113,1 225319534991831177328890236228992001350685163362356544091911 false 23269086799180847,1,9683213481319911991636641541802024271084713,1

18、35375166993717494840635767087951744212057570647889977422429871 false 1381,1,1867,1,8311930927,1,38893867968570583,1,42440201875440880489113304753,1 5766152219975951659023630035336134306565384015606066319856068811 false6)n=455766152219975951659023630035336134306565384015606066319856068811 false 1361,

19、1,214114727210560829,1,32267019267402210517,1,613228865630544238382107,1 962947420735983927056946215901134429196419130606213075415963491271 false 205590139,1,53252429177,1,7064576339566763,1,12450154709928940906197946067239,1 166589903787325219380851695350896256250980509594874862046961683989711 fals

20、e 62614127,1,2660580156093611580352333193927566158528098772260689062181793,1 29819592777931214269172453467810429868925511217482600306406141434158091 false 601,1,1651781,1,8564177,1,358995947,1,1525310189119,1,6405328664096618954809029861252251,1 539734629280554978272021407767368780627551753036435065

21、5459511599582614291 false 107453,1,5634838141,1,8914157280964101123344891396571257163632974628403174028667,1 1030893141925860008499560888835674370998623848299590975192766715520279329391 false 32999,1,175603474759,1,77148541513247,1,2305961466437323959598530415862423316227152033,1 1989623763916909816

22、40415251545285153602734402721821058212203976095413910572271 false 21639496447,1,7979125905967339495018877,1,1152307771625979758044020162101777453615909,1 39195588149163123383161804554421175259738677336198748467804183290796540382737191 false 521831,1,50257723,1,1601684368321,1,39081170243262541027,1,

23、23875913958369977158572653160969521,1 false 实验观察与分析：当时并不都是素数，如果不是，能表示成几个素因子相乘的形式。根据以上的结果，猜测素数是有无穷多个.证明：反证法，若素数的个数是有限的，且最大的素数是pk。令n=p1p2.pk+1，npk，则n是合数，根据算术基本定理，n存在素因 子p，则 可得出pp1p2.pk，且pn p1，这与p是素数相矛盾。 故而假设不成立。 得证：素数的个数是无穷多个的。2.eratosthenes筛法与试除法通过eratosthenes筛法求1000以内的素数并计时，程序如下： sieven_integer:= mo

24、dule t=,i,temp, fori=2,i=n,i+,appendtot,i; fori=1,primei=sqrtn,i+,temp=primei; t=selectt,(#1=temp|mod#1,temp!=0)&; t sieve1000运行结果;2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,22

25、9,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,69

26、1,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997sieven_integer:= module t=,i,temp, fori=2,i=n,i+,appendtot,i; fori=1,primei=sqrtn,i+,temp=primei; t=selectt,(#1=temp|mod#1,temp

27、!=0)&; timingsieve1000运行结果为; 0.032 second,null即用eratosthenes筛法求1000以内的素数所用的时间是0.032。用试除法求1000以内的素数并计时，程序如下： divprimen_integer:= module t=,i,j,temp,divided, fori=2,i=n,i+, j=1;divided=false; whileprimej=sqrti&(!divided), temp=primej; divided=(modi,temp=0);j=j+1; if!divided,appendtot,i; t divprime1000

28、运行结果为;2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419

29、,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911

30、,919,929,937,941,947,953,967,971,977,983,991,997divprimen_integer:= module t=,i,j,temp,divided, fori=2,i=n,i+, j=1;divided=false; whileprimej=sqrti&(!divided), temp=primej; divided=(modi,temp=0);j=j+1; if!divided,appendtot,i;timingdivprime1000运行结果为：0.14 second,null即用试除法求1000以内的素数所用的时间是0.14.由以上程序的结果可

31、得，eratosthenes筛法比试除法的时间要快，故而可得eratosthenes筛法比试除法要好3素数的判别公式对n=2 ,3 , 200,观察m （n - 1)被n整除所得的余数. 当m=2时 运行如下程序：mn_integer:=moduley,k,m=2;k=m(n-1);x=modk,n; printn, ,primeqn, ,x, ,gcdm,ndomn,n,2,200运行结果为：2 true 0 2 3 true 1 1 4 false 0 2 5 true 1 1 6 false 2 2 7 true 1 1 8 false 0 2 9 false 4 1 10 false

32、2 2 11 true 1 1 12 false 8 2 13 true 1 1 14 false 2 2 15 false 4 1 16 false 0 2 17 true 1 1 18 false 14 2 19 true 1 1 20 false 8 2 21 false 4 1 22 false 2 2 23 true 1 1 24 false 8 2 25 false 16 1 26 false 2 2 27 false 13 1 28 false 8 2 29 true 1 1 30 false 2 2 31 true 1 1 32 false 0 2 33 false 4 1 3

33、4 false 2 2 35 false 9 1 36 false 32 2 37 true 1 1 38 false 2 2 39 false 4 1 40 false 8 2 41 true 1 1 42 false 32 2 43 true 1 1 44 false 8 2 45 false 31 1 46 false 2 2 47 true 1 1 48 false 32 2 49 false 15 1 50 false 12 2 51 false 4 1 52 false 8 2 53 true 1 1 54 false 14 2 55 false 49 1 56 false 16

34、2 57 false 4 1 58 false 2 2 59 true 1 1 60 false 8 2 61 true 1 1 62 false 2 2 63 false 4 1 64 false 0 2 65 false 16 1 66 false 32 2 67 true 1 1 68 false 8 2 69 false 4 1 70 false 22 2 71 true 1 1 72 false 32 2 73 true 1 1 74 false 2 2 75 false 34 1 76 false 8 2 77 false 9 1 78 false 32 2 79 true 1 1

35、 80 false 48 2 81 false 40 1 82 false 2 2 83 true 1 1 84 false 32 2 85 false 16 1 86 false 2 2 87 false 4 1 88 false 40 2 89 true 1 1 90 false 32 2 91 false 64 1 92 false 8 2 93 false 4 1 94 false 2 2 95 false 54 1 96 false 32 2 97 true 1 1 98 false 58 2 99 false 58 1 100 false 88 2 101 true 1 1 102

36、 false 32 2 103 true 1 1 104 false 24 2 105 false 46 1 106 false 2 2 107 true 1 1 108 false 68 2 109 true 1 1 110 false 72 2 111 false 4 1 112 false 64 2 113 true 1 1 114 false 32 2 115 false 39 1 116 false 8 2 117 false 22 1 118 false 2 2 119 false 30 1 120 false 8 2 121 false 56 1 122 false 2 2 12

37、3 false 4 1 124 false 8 2 125 false 91 1 126 false 32 2 127 true 1 1 128 false 0 2 129 false 4 1 130 false 122 2 131 true 1 1 132 false 68 2 133 false 64 1 134 false 2 2 135 false 94 1 136 false 128 2 137 true 1 1 138 false 32 2 139 true 1 1 140 false 128 2 141 false 4 1 142 false 2 2 143 false 114

38、1 144 false 32 2 145 false 16 1 146 false 2 2 147 false 25 1 148 false 8 2 149 true 1 1 150 false 62 2 151 true 1 1 152 false 128 2 153 false 103 1 154 false 8 2 155 false 109 1 156 false 20 2 157 true 1 1 158 false 2 2 159 false 4 1 160 false 128 2 161 false 156 1 162 false 122 2 163 true 1 1 164 f

39、alse 8 2 165 false 16 1 166 false 2 2 167 true 1 1 168 false 32 2 169 false 40 1 170 false 2 2 171 false 85 1 172 false 8 2 173 true 1 1 174 false 32 2 175 false 134 1 176 false 32 2 177 false 4 1 178 false 2 2 179 true 1 1 180 false 68 2 181 true 1 1 182 false 2 2 183 false 4 1 184 false 128 2 185

40、false 16 1 186 false 32 2 187 false 174 1 188 false 8 2 189 false 67 1 190 false 132 2 191 true 1 1 192 false 128 2 193 true 1 1 194 false 2 2 195 false 4 1 196 false 64 2 197 true 1 1 198 false 194 2 199 true 1 1 200 false 88 2从运行结果可以发现:当n为素数时，2(n-1)被n整除所得的余数都是1。那么，再取其他的整数m=3, 观察3 (n - 1)被n整除所得的余数.

41、 运行如下程序: mn_integer:=moduley,k,m=3;k=m(n-1);x=modk,n; printn, ,primeqn, ,gcdm,n, ,x domn,n,2,200运行结果为：2 true 1 1 3 true 3 0 4 false 1 3 5 true 1 1 6 false 3 3 7 true 1 1 8 false 1 3 9 false 3 0 10 false 1 3 11 true 1 1 12 false 3 3 13 true 1 1 14 false 1 3 15 false 3 9 16 false 1 11 17 true 1 1 18 false 3 9 19 true 1 1 20 false 1 7 21 false 3 9 22 false 1 3