大学数学实验报告-素数

数学实验报 告实验五素数班级：09（4）班姓名：***学号：***实验五素数实验素数名称实验掌握素数的含义及其性质,并能熟练的运用素数的判别与求解、生成素目的数的公式、素数的分布；学会探讨素数的规律及其相关的某些有趣的问实验Mathematica4.0环境实验1、用Eratosthenesn的基2FermatMersenne本理3、生成素数的公式有n2+n+41,n2-79n+1601,6n2+6n+31；论与4方法一、素数的产生、求解及判别1、素数的产生程序实验TablePrimen,n,25的内容与步骤2、素数的求解利用Eratosthenes1000输入程序：.Sieven_Integer:ModuleFori

t2,

,i,temp,n,i,AppendTot,iFori

1,Prime

Sqrtn,

,

PrimeitSelectt,#1

temp

Mod#1,

0& tSieve1000运行结果：1000输入程序：DivPrimen_Integer:Modulet ,i,j,temp,divided,Fori2,in,i,j1dividedFalseWhilePrimej Sqrti&& divided,tempPrimejdivided Modi,temp 0jj1Ifdivided,AppendTot,i tDivPrime1000运行结果：判断Eratosthenes取n=1000Sieven_Integer:ModuletFor

,i,temp,2,i n,i,AppendTot,iFor

1,Prime

Sqrtn,

,

PrimeitSelectt,#1

Mod#1,temp 0&TimingSieve1000运行结果：Sieven_Integer:Modulet,i,temp,Fori 2,i n,i,AppendTot,i;Fori 1,Primei Sqrtn,i ,tempt Selectt,#1 temp Mod#1,temTimingSieve1000

Primei0& ;0.031NullSecond,输入程序：DivPrimen_Integer:ModuletFor

,i,j,temp,divided,2,i n,i,j1dividedFalseWhilePrimej Sqrti&& divided,tempPrimejdivided Modi,temp 0jj1Ifdivided,AppendTot,iTimingDivPrime1000运行结果：DivPrimen_Integer:Modulet ,i,j,temp,divided,Fori 2,i n,i ,j1;dividedFalse;WhilePrimejSqrti&& divided,temp Primej;divided Modi,temp 0;j j 1If divided,AppendTot,i ;TimingDivPrime10000.156NullSecond,n=10000时，程序如下：Sieven_Integer:ModuletFor

,i,temp,2,i n,i,AppendTot,iFor

1,Prime

Sqrtn,

,

PrimeitSelectt,#1

Mod#1,temp 0&TimingSieve10000运行结果：Sieven_Integer:Modulet ,i,temp,Fori 2,i n,i ,AppendTot,i Fori 1,Primei Sqrtn,i ,tempt Selectt,#1 temp Mod#1,tempTimingSieve10000

Primei0& ;2.11NullSecond,输入程序：DivPrimen_Integer:Modulet ,i,j,temp,divided,Fori 2,i n,i ,j1;dividedFalse;WhilePrimejSqrti&& divided,temp Primej;divided Modi,temp 0;j j 1If divided,AppendTot,i ;TimingDivPrime10000运行结果：DivPrimen_Integer:Modulet ,i,j,temp,divided,Fori 2,i n,i ,j 1;divided False;WhilePrimej Sqrti&& dividedtemp Primej;divided Modi,temp 0;j j 1If divided,AppendTot,i ;TimingDivPrime100002.NullSecond,3、素数的判别(1n=2,3,…,1002n-1nm（如34，观察mn-1被n整除的情况：观察当nm=2输入程序：Mn_Integer:Module y,k,m 2;k m^n 1;x Modk,n;Printn," ",PrimeQn," ",x," ",GCDm,nDoMn,n,2,100运行结果：Mn_Integer:Module y,k,m 2;k m^n 1;x Modk,n;Printn," ",PrimeQn," ",x," ",GCDm,nDoMn,n,2,1002True023True114False025True116False227True118False029False4110False2211True1112False8213True1114False2215False4116False0217True1118False14219True1120False8221False4122False2223True1124False8225False16126False2227False13128False8229True1130False2231True1132False0233False4134False2235False9136False32237True1138False2239False4140False8241True1142False32243True1144False8245False31146False2247True1148False32249False15150False12251False4152False8253True1154False14255False49156False16257False4158False2259True1160False8261True1162False2263False4164False0265False16166False32267True1168False8269False4170False22271True1172False32273True1174False2275False34176False8277False9178False32279True1180False48281False40182False2283True1184False32285False16186False2287False4188False40289True1190False32291False64192False8293False4194False2295False54196False32297True1198False58299False581100Null2

88 2从运行结果可以发现:当n2^n-1被n整除所得的余数都是m=3输入程序：Mn_Integer:ModulexModk,n

y,k,m3km^n1Printn,"",PrimeQn," ",GCDm,n," ",xDoMn,n,2,100运行结果：Mn_Integer:Module y,k,m 3;k m^n 1x Modk,n;Printn," ",PrimeQn," ",GCDm,n," ",DoMn,n,2,1002True113True304False135True116False337True118False139False3010False1311True1112False3313True1114False1315False3916False11117True1118False3919True1120False1721False3922False1323True1124False3325False1626False1327False3028False12729True1130False3331True1132False11133False3934False1335False1436False32737True1138False1339False3940False12741True1142False33343True1144False12745False33646False1347True1148False32749False14350False13351False3952False12753True1154False32755False1456False1357False3958False1359True1160False32761True1162False1363False3964False14365False11666False34567True1168False12769False3970False11371True1172False32773True1174False1375False36976False12777False12578False3979True1180False12781False3082False1383True1184False37585False18186False1387False3988False17589True1190False36391False1192False12793False3994False1395False12496False37597True1198False15999False327100False167Null2m=4输入程序：Mn_Integer:ModulexModk,n

y,k,m4km^n1Printn,"",PrimeQn," ",GCDm,n," ",xDoMn,n,2,100运行结果：Mn_Integer:ModulexModk,n

y,k,m4km^n1Printn,

",PrimeQn," ",GCDm,n,

",xDoMn,n,2,1002True203True114False405True116False247True118False409False1710False2411True1112False4413True1114False2415False1116False4017True1118False21619True1120False4421False11622False2423True1124False41625False1626False2427False1728False4829True1130False2431True1132False4033False11634False2435False11136False41637True1138False2439False11640False42441True1142False21643True1144False42045False11646False2447True1148False41649False12950False24451False11652False41253True1154False23455False13656False43257False11658False2459True1160False4461True1162False2463False11664False4065False16166False23467True1168False46469False11670False26471True1172False41673True1174False2475False13176False46477False1478False21079True1180False46481False16182False2483True1184False41685False1186False2487False11688False41689True1190False23491False1192False46493False11694False2495False16696False46497True1198False23299False197100False 4 44（2）对n=2,3,..,300,判断哪些Mersenne数输入程序：t 1;Forn 2,n 100,n ,Printn,"",PrintQn,"",2^n 1,FactorInteger2^n 1运行结果：t 1;Forn 2,n 100,n ,Printn,"",PrintQn,"",2^n 1FactorInteger2^n 12PrintQ233,13PrintQ377,14PrintQ4153,1,5,15PrintQ53131,16PrintQ6633,2,7,17PrintQ7127127,18PrintQ82553,1,5,1,17,19PrintQ95117,1,73,110PrintQ1010233,1,11,1,31,111PrintQ11204723,1,89,112PrintQ1240953,2,5,1,7,1,13,113PrintQ1381918191,114PrintQ14163833,1,43,1,127,115PrintQ15327677,1,31,1,151,116PrintQ16655353,1,5,1,17,1,257,117PrintQ17131071131071,118PrintQ182621433,3,7,1,19,1,73,119PrintQ19524287524287,120PrintQ2010485753,1,5,2,11,1,31,1,41,121PrintQ2120971517,2,127,1,337,122PrintQ2241943033,1,23,1,89,1,683,123PrintQ23838860747,1,178481,124PrintQ24167772153,2,5,1,7,1,13,1,17,1,241,125PrintQ253355443131,1,601,1,1801,126PrintQ26671088633,1,2731,1,8191,127PrintQ271342177277,1,73,1,262657,128PrintQ282684354553,1,5,1,29,1,43,1,113,1,127,129PrintQ29536870911233,1,1103,12089,130PrintQ3010737418233,2,7,1,11,1,31,1,151,1,331,131PrintQ3121474836472147483647,132PrintQ3242949672953,1,5,1,17,1,257,1,65537,133PrintQ3385899345917,1,23,1,89,1,599479,134PrintQ3417191833,1,43691,1,131071,135PrintQ353435973836731,1,71,1,127,1,122921,136PrintQ36687194767353,3,5,1,7,1,13,1,19,1,37,1,73,1,109,137PrintQ37137438953471223,1,616318177,138PrintQ382748779069433,1,174763,1,524287,139PrintQ395497558138877,1,79,1,8191,1,121369,140PrintQ4010995116277753,1,5,2,11,1,17,1,31,1,41,1,61681,141PrintQ41219902325555113367,1,164511353,142PrintQ4243980465111033,2,7,2,43,1,127,1,337,1,5419,143PrintQ438796093022207431,1,9719,1,2099863,144PrintQ44175921860444153,1,5,1,23,1,89,1,397,1,683,1,2113,145PrintQ45351843720888317,1,31,1,73,1,151,1,631,1,23311,146PrintQ46703687441776633,1,47,1,178481,1,2796203,147PrintQ471407374883553272351,1,4513,1,13264529,148PrintQ482814749767106553,2,5,1,7,1,13,1,17,1,97,1,241,1,257,1,673,1PrintQPrintQ

5629499534213111125899906842623

127,1,4432676798593,13,1,11,1,31,1,251,1,601,1,1801,1,4051,151PrintQ5122517998136852477,1,103,1,2143,1,11119,1,131071,152PrintQ5245035996273704953,1,5,1,53,1,157,1,1613,1,2731,1,8191,153PrintQ5390071992547409916361,1,69431,1,20394401,154PrintQ54180143985094819833,4,7,1,19,1,73,1,87211,1,262657,155PrintQ553602879701896396723,1,31,1,89,1,881,1,3191,1,201961,156PrintQ56720575940379279353,1,5,1,17,1,29,1,43,1,113,1,127,1,15790321,157PrintQ571441151880758558717,1,32377,1,524287,1,1212847,158PrintQ582882303761517117433,1,59,1,233,1,1103,1,2089,1,3033169,159PrintQ59576460752303423487179951,1,3203431780337,160PrintQ6011529215046068469753,2,5,2,7,1,11,1,13,1,31,1,41,1,61,1,151,1,331,1,1321,161PrintQ6123058430092136939512305843009213693951,162PrintQ6246116860184273879033,1,715827883,1,2147483647,163PrintQ6392233720368547758077,2,73,1,127,1,337,1,92737,1,649657,164PrintQ64184467440737095516153,1,5,1,17,1,257,1,641,1,65537,1,6700417,165PrintQ653689348814741910323131,1,8191,1,145295143558111,166PrintQ66737869762948382064633,2,7,1,23,1,67,1,89,1,683,1,20857,1,599479,167PrintQ67147573952589676412927193707721,1,761838257287,168PrintQ682951479051793528258553,1,5,1,137,1,953,1,26317,1,43691,1,131071,169PrintQ695902958103587056517117,1,47,1,178481,1,10052678938039,170PrintQ7011805916207174113034233,1,11,1,31,1,43,1,71,1,127,1,281,1,86171,1,122921,171PrintQ712361183241434822606847228479,1,48544121,1,212885833,172PrintQ7247223664828696452136953,3,5,1,7,1,13,1,17,1,19,1,37,1,73,1,109,1,241,1,433,1,38737,173PrintQ739444732965739290427391439,1,2298041,1,9361973132609,174PrintQ74188894659314785808547833,1,223,1,1777,1,25781083,1,616318177,175PrintQ75377789318629571617095677,1,31,1,151,1,601,1,1801,1,100801,1,10567201,176PrintQ76755578637259143234191353,1,5,1,229,1,457,1,174763,1,524287,1,525313,177PrintQ7715111572745182864683827123,1,89,1,127,1,581283643249112959,178PrintQ783022314549036572936765433,2,7,1,79,1,2731,1,8191,1,121369,1,22366891,179PrintQ796044629098073145873530872687,1,202029703,1,1113491139767,180PrintQ8012089258196146291747061753,1,5,2,11,1,17,1,31,1,41,1,257,1,61681,1,4278255361,181PrintQ8124178516392292583494123517,1,73,1,2593,1,71119,1,262657,1,97685839,182PrintQ8248357032784585166988247033,1,83,1,13367,1,164511353,1,8831418697,183PrintQ839671406556917033397649407167,1,57912614113275649087721,184PrintQ84193428131138340667952988153,2,5,1,7,2,13,1,29,1,43,1,113,1,127,1,337,1,1429,1,5419,1,14449,185PrintQ853868562622766813359059763131,1,131071,1,9520972806333758431,186PrintQ86773712524553362671811952633,1,431,1,9719,1,2099863,1,2932031007403,187PrintQ871547425049106725343623905277,1,233,1,1103,1,2089,1,4177,1,9857737155463,188PrintQ883094850098213450687247810553,1,5,1,17,1,23,1,89,1,353,1,397,1,683,1,2113,1,2931542417,189PrintQ89618970019642690137449562111618970019642690137449562111,190PrintQ9012379400392853802748991242233,3,7,1,11,1,19,1,31,1,73,1,151,1,331,1,631,1,23311,1,18837001,191PrintQ912475880078570760549798248447127,1,911,1,8191,1,112901153,1,23140471537,192PrintQ9249517601571415210995964968953,1,5,1,47,1,277,1,1013,1,1657,1,30269,1,178481,1,2796203,193PrintQ9399035203142830421991929937917,1,2147483647,1,658812288653553079,194PrintQ94198070406285660843983859875833,1,283,1,2351,1,4513,1,13264529,1,165768537521,195PrintQ953961408125713216879677197516731,1,191,1,524287,1,420778751,1,30327152671,196PrintQ96792281625142643375935439503353,2,5,1,7,1,13,1,17,1,97,1,193,1,241,1,257,1,673,1,65537,1,22253377,197PrintQ9715845632502852867518708790067111447,1,13842607235828485645766393,198PrintQ983169126500570573503741758013433,1,43,1,127,1,4363953127297,1,4432676798593,199PrintQ996338253001141147007483516026877,