素数实验报告

1、实验报告1实验目的（1）要知道素数的定义，并且要会用软件编程利用计算机运行试除法和eratosthenes筛选求出要求的所有的素数。并且会比较两种方法的优缺点。（2）会用软件编程并且利用计算机运行mersenne数，求出最大素数。（3）了解fermat数，尝试着寻找一个多项式p（x1,x2,x3 . ）其正值正好构成的集合恰好是素数的全体。（4）掌握对于一个给定的数，求出小于等于此数的所有素数，并在数轴上表示出来，观察素数的分布。（5）了解goldbach猜想，大整数的素因子分解，完全数，孪生素数，bertrand猜测和青一色数的素数。2实验解读（1）素数的判别与求解素数的定义：如果一个大于1

2、的自然数只能被1及它本身整除，则其为素数，否则为和数。要求出给定范围内的所有素数有两种方法，第一种：试除法，已知前n个素数，他们从小到大排列为p1=2, p2=3,pn,对n=1,2,320.计算n=p1*p2*p3.*pn+1,判断n是否都是素数，多次尝试从而求出要求的 素数 。第二种：eratosthenes筛选，其是将自然数从2开始按顺序排列至某一整数n，首先，从数列中划除所有2的倍数，不包括2，在剩下的树中划掉所有3的倍数，不包括3，再在剩下的树中划掉所有5的倍数，不包括5，则最后剩下的树就是不超过n的所有素数。（2）最大素数利用mersenne数求出例如由2n-1构造出的最大素数，并

3、且mersenne数极其稀少，目前为止，科学家仅仅发现34个mersenne数。判断mersenne数是否为素数，假定n为素数，定义数列u1=4,uk+1=uk2-2 modmn k=1,2,3n.如果un-1=0 mod mn,则mn为素数，否则为合数。（3）构成生成素数的公式先前大数学家fermat提出fn=2(2n)+1永远是素数，但当n为5，6，7，8，9，10时，其不为素数，均为合数。至今为止科学家未能给出具体的公式。马蒂雅舍维奇证明了：存在一个多项式p（x1,x2,x3 . ）其正值正好构成的集合恰好是素数的全体。但其未能给出具体多项式。（4）素数的分布素数的分布很不规则，它虽然沿

4、数轴分布越来越稀，但有时素数之间的间隔又很小，总之，固定区间长度内的素数个数越来越少。3实验思路大致算法如下：（1）试除法numpn_integer:= modulei,num, num=productprimei,i,1,n+1; printn, ,num, ,primeq num, ,factorintegernum donumpn,n,1,20（2）eratosthenes筛选eratosthenes筛选，其是将自然数从2开始按顺序排列至某一整数n，首先，从数列中划除所有2的倍数，不包括2，在剩下的树中划掉所有3的倍数，不包括3，再在剩下的树中划掉所有5的倍数，不包括5，则最后剩下的树就

5、是不超过n的所有素数。 sieven_integer:= module t=,i,temp, fori=2,i=n,i+,appendtot,i; fori=1,primei=sqrtn,i+,temp=primei; t=selectt,(#1temp|mod#1,temp!=0)&; tsieven（3）mersenne数ersennen_integer:= module m,i,u=4 , if !primeqn , false , m=2n-1; fori=1,in-1,i+,u=modu2-2,m; , if u 0 , true , false （4）素数的分布comparen_i

6、nteger:= modulex,k,t= li=nintegrate1/loge,x,x,2,n; r=1+nsum1/k/zetak+1*loge,nk/factorialk, k,2,infinity; appendtot,primepin; appendtot,nn/loge,n; appendtot,nn/(loge,n-1.08366); appendtot,li; appendtot,r; printtdocomparei,i,100000,900000,100000comparen4实验过程及相应结果1.数的判别与求解试除法 已知前n个素数，他们从小到大排列为p1=2, p2=

7、3,pn,对n=1,2,320.计算n=p1*p2*p3.*pn+1,判断n是否都是素数，多次尝试,得出结果.编写mathematica程序如下： numpn_integer:= modulei,num, num=productprimei,i,1,n+1; printn, ,num, ,primeq num, ,factorintegernum donumpn,n,1,20运行程序得出结果如下：1 3 true 3,12 7 true 7,13 31 true 31,14 211 true 211,15 2311 true 2311,16 30031 false 59,1,509,17 51

8、0511 false 19,1,97,1,277,18 9699691 false 347,1,27953,19 223092871 false 317,1,703763,110 6469693231 false 331,1,571,1,34231,111 200560490131 true 200560490131,112 7420738134811 false 181,1,60611,1,676421,113 304250263527211 false 61,1,450451,1,11072701,114 13082761331670031 false 167,1,783398882135

9、93,115 614889782588491411 false 953,1,46727,1116 32589158477190044731 false 73,1,139,1,173,1,18564761860301,117 1922760350154212639071 false 277,1,3467,1,105229,1,19026377261,118 117288381359406970983271 false 223,1,525956867082542470777,119 7858321551080267055879091 false 54730729297,1

10、,143581524529603,120 557940830126698960967415391 false 1063,1,303049,1,598841,1,2892214489673,1eratosthenes筛选实验思路: eratosthenes筛选，其是将自然数从2开始按顺序排列至某一整数n，首先，从数列中划除所有2的倍数，不包括2，在剩下的树中划掉所有3的倍数，不包括3，再在剩下的树中划掉所有5的倍数，不包括5，则最后剩下的树就是不超过n的所有素数。编写mathematica程序如下：sieven_integer:= module t=,i,temp, fori=2,i=n,i+,

11、appendtot,i; fori=1,primei=sqrtn,i+,temp=primei; t=selectt,(#1temp|mod#1,temp!=0)&; tsieven当n=100时运行程序得出结果如下：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制成表格如下：2357111317192329313741434753596167717379838997改进之后的实验思路：假设已经找到前n个素数p1=2,p2=3,p3=5.为了寻找下一个素数就从pn+2开始依次检验每一个整数n，看n是否

12、能被某个pn整除，如果n能被前面的某个素数整除，则n为合数，否则n即为下一个素数pn+1改进之后的程序如下：divprimen_integer:= module t=,i,j,temp,divided, fori=2,in,i+, j=1;divided=false; whileprimejsqrti&(!divided), temp=primej; divided=(modi,temp0);j=j+1; if!divided,appendtot,i ; tdivprimen当n=1000时，运行结果如下：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,

13、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,421,431,433,439,443,449,457,461,463,467,479,487,4

14、91,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,919,929,937,941,947,953,967,971,977,983,991,997me

15、rsenne数对n=2,3,4.300,判断哪些mersenne数mn=2n-1是素数？，如果n为合数，mersenne数是合数还是素数？如果n为素数，mersenne数是否一定为素数？为了验证以上问题编写mathematica程序如下：mn_integer:=moduley,k,m=2;k=m(n-1);x=modk,n; printn, ,primeqn, ,x, ,gcdm,ndomn,n,2,300运行结果如下：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

16、4 1 10 false 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 3

17、3 false 4 1 34 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

18、 56 false 16 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 1112 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

19、 122 false 2 2 123 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

20、 2 143 false 114 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 1

21、63 true 1 1 164 false 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

22、 false 128 2 185 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 ,3,4100,观察 被n整除所得的余数，观察得出结论，在取其他的整数m（如2,3,4）观察被n整除

23、的情况编写mathematica程序如下：mn_integer:=moduley,k,m=3;k=m(n-1);x=modk,n; printn, ,primeqn, ,x, ,gcdm,ndomn,n,2,20当为3n-1时，运行取前20个结果结果如下：2 true 1 1 3 true 0 3 4 false 3 1 5 true 1 1 6 false 3 3 7 true 1 1 8 false 3 1 9 false 0 3 10 false 3 1 11 true 1 1 12 false 3 3 13 true 1 1 14 false 3 1 15 false 9 3 16 f

24、alse 11 1 17 true 1 1 18 false 9 3 19 true 1 1 20 false 7 1当为4n-1时，运行取前20个结果结果如下：2 true 0 2 3 true 1 1 4 false 0 4 5 true 1 16 false 4 2 7 true 1 1 8 false 0 4 9 false 7 1 10 false 4 2 11 true 1 1 12 false 4 4 13 true 1 1 14 false 4 2 15 false 1 1 16 false 0 4 17 true 1 1 18 false 16 2 19 true 1 1 2

25、0 false 4 4当为5n-1时，运行取前20个结果结果如下：2 true 1 1 3 true 1 1 4 false 1 1 5 true 0 5 6 false 5 1 7 true 1 1 8 false 5 1 9 false 7 1 10 false 5 5 11 true 1 1 12 false 5 1 13 true 1 1 14 false 5 1 15 false 10 5 16 false 13 1 17 true 1 1 18 false 11 1 19 true 1 1 20 false 5 52生成素数的公式给出format的mathematica程序如下：f

26、ormatn_integer:= modulem,m=2(2(n)+1; printn, , primeqm dofermatn ,n,1,10 运行结果如下： 1 true 2 true 3 true 4 true 5 false 6 false 7 false 8 false 9 false 10 false3素数的分布对于n=0,1,2,3，。100计算n2 + n +41。它们是否都给出素数？在10000内的素数中，由公式n2 + n +41给出的素数占多少？类似的对n2-79n+1601及6n2+6n+31做同样的判断。对于n2 + n +41编写mathematica程序如下： t

27、=0;eun_integer := moduley ,y= n2 + n +41; ifprimeqytrue, t=t+1;doeun ,n,1,10000 printt 运行结果如下：4148所以在10000内的素数有4148个素数。对于n2-79n+1601编写mathematica程序如下：t=0;eun_integer := moduley ,y=n2-79n+1601; ifprimeqytrue, t=t+1;doeun ,n,1,10000 printt 运行结果如下：4148所以在10000内的素数有4148个素数。对于6n2+6n+31编写mathematica程序如下：t

28、=0;eun_integer := moduley ,y=6n2+6n+31; ifprimeqytrue, t=t+1;doeun ,n,1,10000 printt 运行结果如下：3858所以在10000内的素数有3858个素数 （1）超过素数n的个数pi(m n )表示区间【m n】的个数编写mathematica程序如下：t:=tablei,primepi 2i+100-primepi2i,i,1,40listplott,plotstylergbcolor0,0,1,plotjoinedtrue图像如下：实验结论：有图像可知随着区间的增大，其素数分布越来越散。（2）将素数从小到大的循序

29、排列：p1 p2 p3 .用dn=pn+1-pn表示相邻的素数之间的间隔，计算d1 d2 d3 d4.编写mathematica程序如下：t:=tablei,primepi i+100-primepi i,i,100000,101000,100listplott,plotstylergbcolor0,0,1,pointsize0.04绘制出图像绘制成折线图如下：实验结论：有图像可知随着区间的增大，其间隔越来越大,。（3）在二维坐标平面标出点列（n,pi(n)）,n=1,2,3.并且用折线图表示出，观察pi(n)趋于无穷的趋势，将它同y=x,y= 比较。编写同y=mathematica程序如下：

30、f=listplottablen,primepin/n,n,2,10000 , plotstylergbcolor1,0,0,plotjoinedtrue,displayfunctionidentity g=listplottablen,primepin/sqrtn,n,2,10000 , plotstylergbcolor0,1,0,plotjoinedtrue , displayfunctionidentity h=listplottablen,primepin/n/log10,n,n,2,10000 , plotstylergbcolor0,0,1,plotjoinedtrue,disp

31、layfunctionidentity showf,g,h, displayfunction$displayfunction绘制成图如下：编写同y=x 的 mathematica程序如下：b=tablen,primepin,n,2,10000;ft=fitb,1,x,xg=plotft,x,2,10000,plotstylergbcolor1,0,0 , displayfunctionidentityf=listplotb,plotstylergbcolor0,1,0 , displayfunctionidentityshowg,f,displayfunction$displayfunctio

32、n绘制成图如下： y=60.9457 +0.118897 x（4）令 其中对于一系列充分大的n计算li(n) r(n)其中那个公式更接近pi(n)?编写mathematica程序如下：comparen_integer:= modulex,k,t=, li=nintegrate1/loge,x,x,2,n; r=1+nsum1/k/zetak+1*loge,nk/factorialk, k,2,infinity; appendtot,primepin ; appendtot,nn/loge,n; appendtot, ; appendtot,nn/(loge,n-1.08366); appendtot, ; appendtot,li; appendtot,r; print tdocomparei,i