探索实验 素数.doc

探索实验 素数一 实验指导书解读如果一个大于1的自然数只能被1及它本身整除，则该数称为素数，否则称为合数。从数学史的黎明时期开始，数学家们就一直在探索自然数的奥秘。远在古希腊时代，欧几里得就证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时这种分析师唯一的，这就是所谓的算术基本定理。算术基本定理表明，素数是构造自然数的基石，正如物质的基本粒子一样。正是由于素数如此重要的地位才使得一代一代数学家努力地探索素数的规律。素数到底是什么？会不会在某一充分大的自然数以后就没有素数呢？通过本章探究实验，我们需要知道素数怎么判别，有什么方法几种方法判别？到底有没有一个明确的判别素数的准则。对于一些特殊的数，我们又有什么特殊的方法判别呢？然后我们需要解决怎样求解小于某一给定整数N的所以素数的方法，即素数的求解关于素数的求解，我们通过Eratosthenes筛法和试除法验证求解。Eratosthenes筛法的基本思想是：将自然数列从2开始按顺序排列至某一整数N，首先，从上述数列中划去所以2的倍数（不包括2），在剩下的数里，从数列中划掉3的倍数（不包括3），然后再剩下的数中，再划去5的倍数。这个过程一直进行下去，则最后剩下的数就是不超过N的所有素数。试除法的基本思想是：假设我们已经找到了前n个素数p1,p2,.pn,为了寻找下一个素数我们从pn+2开始一次检验每一个整数N，看N是否能被某个pi（i=1,2,n）整除。如果N 能被前面的某个素数整除，则N为合数。否则N为下一个素数。虽然这两种方法都能求解问题，但是哪一个更有效呢？它们又有什么缺陷呢？从理论上来说，这两种方法可以求出所有的素数，但是经过试验我们会发现它们不能构造出大的素数表，那我们经过试验探索，又能得到什么更好的方法呢？接下来我们需要考虑的问题就是怎么生成素数，我们能否找到一个正好生成全部素数的公式。求解了素数的判别生成，那到底素数是不是有规则，有什么特殊的规则呢？二 试验计划练习一 素数的判别（1）NumPn_Integer:= Modulei,Num, Num=ProductPrimei,i,1,n+1; Printn, ,Num, ,PrimeQ Num, ,FactorIntegerNum DoNumPn,n,1,20实验思路：取n=1,2,20,判断Nn是否为素数；取n=2025时呢？进一步猜测素数是否有无穷多个。若Nn不是素数，Nn是否含有不同的素因子？（2）Mn_Integer:=Moduley,k,m=2;k=m(n-1);x=Modk,n; Printn, ,PrimeQn, ,x, ,GCDm,nDoMn,n,2,200实验思路：其中此程序中m取2，观察余数，能得出什么结论。当m取3,4,5,时，观察余数，我们得出什么结论？若再取一系列的数，我们是否还能得到相同的结论？练习二 素数的求解Eratosthenes筛法Sieven_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!=0)&; tSieve10000试除法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; tDivPrime1000实验思路：分别用Eratosthenes筛法和试除法两种方法求10000以内的所以素数，然后将两种方法比较，看哪一种更有效些练习三 素数的生成Fermat公式生成素数Fermatn_Integer:= Modulem,m=2(2(n)+1; Printn, , PrimeQm DoFermatn ,n,1,10 公式n2 + n +41;生成素数t=0;Eun_Integer := Moduley ,y= n2 + n +41; IfPrimeQyTrue, t=t+1;DoEun ,n,1,100 Printt 实验思路：,Fermat公式能否生成所以素数，取n=1,2,3,4验证，再取n=5,6,7,8,9,10等验证,Fermat公式只能生成有限个素数，那么特殊公式是否都能生成素数？在10000以内的素数中，此公式能给出多少？,对公式n2 -79n +1601 和 6*n2 +6 n +31做与上述相同的判别,根据上述三个实验过程，能否自己推导出一个类似的公式，根据以上的实验你能得出什么结论？ 练习四 素数的分布 t:=Tablei,PrimePi 2i+100-PrimePi2i,i,1,40ListPlott,PlotStyleRGBColor0,0,1,PlotJoinedTrue t:=Tablei,PrimePi 2i+1000-PrimePi2i,i,1,40ListPlott,PlotStyleRGBColor0,0,1,PlotJoinedTrue实验思路：根据上述程序，改变相应变量的值或范围，依次进行以下实验。用(n)表示不超过n的素数的个数，(m,n)表示区间m,n内素数的个数。试计算(100), (1000),(10000)，从计算结果看，我们得出什么结论。随着整数范围的扩大，素数是越来越稀还是越来越密？选取一些更长的区间，再尝试以上同样的实验，看有什么结果。试计算(100,200),(1000,1100),(10000,10100),(100000,100100)，从计算结果看，我们能得出什么结论。随着整数范围的扩大，素数是越来越稀还是越来越密？选取一些更长的区间，再尝试以上同样的实验，看有什么结果。从上述两个实验计算结果观察，随着整数范围的扩大，素数是越来越稀还是越来越密？试着再选取一些更长的区间，再尝试以上同样的实验，看有什么结果t:= Table Primei+1-Primei ,i,1,1000Tt:= TablePrimei,Primei+1-Primei,i,1,1000ListPlott,PlotStyleRGBColor1,0,0实验思路：根据上述程序，改变相应变量的值，依次进行以下实验。1 N取1000，将素数按从小到大的顺序排列：p1=2,p2=3,.,用dn=p(n+1)-pn表示相邻素数间的间隔，将其表示出来，你能从中观察到素数的间隔有什么规律吗？2 计算d1,d2,dn,然后将点(pn,dn)标在平面坐标中。你能从中观察到素数的间隔有什么规律吗？譬如，素数的间隔值有哪些？它们各重复多少次？哪些间隔值的重复次数多？最大最小值是多少？随着N的增大，最大间隔值是否也随之增大呢？ 三 实验过程与结果练习一 1素数的判别（1）NumPn_Integer:= Modulei,Num, Num=ProductPrimei,i,1,n+1; Printn, ,Num, ,PrimeQ Num, ,FactorIntegerNum DoNumPn,n,1,20 1 3 True 3,1 2 7 True 7,1 3 31 True 31,1 4 211 True 211,1 5 2311 True 2311,1 6 30031 False 59,1,509,1 7 510511 False 19,1,97,1,277,1 8 9699691 False 347,1,27953,1 9 223092871 False 317,1,703763,1 10 6469693231 False 331,1,571,1,34231,1 11 200560490131 True 200560490131,1 12 7420738134811 False 181,1,60611,1,676421,1 13 304250263527211 False 61,1,450451,1,11072701,1 14 13082761331670031 False 167,1,78339888213593,1 15 614889782588491411 False 953,1,46727,11 16 32589158477190044731 False 73,1,139,1,173,1,18564761860301,1 17 1922760350154212639071 False 277,1,3467,1,105229,1,19026377261,1 18 117288381359406970983271 False 223,1,525956867082542470777,1 19 7858321551080267055879091 False 54730729297,1,143581524529603,1 20 557940830126698960967415391 False 1063,1,303049,1,598841,1,2892214489673,1实验结果：当n=1,2,3,4,5时，Nn为素数，n=6到20时，Nn是合数。NumPn_Integer:= Modulei,Num, Num=ProductPrimei,i,1,n+1; Printn, ,Num, ,PrimeQ Num, ,FactorIntegerNum DoNumPn,n,20,25 20 557940830126698960967415391 False 1063,1,303049,1,598841,1,2892214489673,1 21 40729680599249024150621323471 False 2521,1,16156160491570418147806951,1 22 3217644767340672907899084554131 False 22093,1,1503181961,1,96888414202798247,1 23 267064515689275851355624017992791 False 265739,1,1004988035964897329167431269,1 24 23768741896345550770650537601358311 False 131,1,1039,1,2719,1,64225891884294373371806141,1 25 2305567963945518424753102147331756071 False 2336993,1,13848803,1,71237436024091007473549,1实验结果:当n=20,21,22,23,24,25时，Nn为合数。实验结论：Nn是否为素数分部并不均匀，没有规律性，所以猜测素数有无穷多个。 Nn不是素数，但是Nn含有不同的素因子(2) 当 m=2的情况 Mn_Integer:=Moduley,k,m=2;k=m(n-1);x=Modk,n; Printn, ,PrimeQn, ,x, ,GCDm,nDoMn,n,2,100 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 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 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 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 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 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实验结果：对于n从2到100这么多数中，含有True的都为素数，而且对于这些素数，2（n-1）（除了2）被n整除所得余数都为1当m=3的情况Mn_Integer:=Moduley,k,m=3;k=m(n-1);x=Modk,n; Printn, ,PrimeQn, ,x, ,GCDm,nDoMn,n,2,100 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 False 11 1 17 True 1 1 18 False 9 3 19 True 1 1 20 False 7 1 21 False 9 3 22 False 3 1 23 True 1 1 24 False 3 3 25 False 6 1 26 False 3 1 27 False 0 3 28 False 27 1 29 True 1 1 30 False 3 3 31 True 1 1 32 False 11 1 33 False 9 3 34 False 3 1 35 False 4 1 36 False 27 3 37 True 1 1 38 False 3 1 39 False 9 3 40 False 27 1 41 True 1 1 42 False 33 3 43 True 1 1 44 False 27 1 45 False 36 3 46 False 3 1 47 True 1 1 48 False 27 3 49 False 43 1 50 False 33 1 51 False 9 3 52 False 27 1 53 True 1 1 54 False 27 3 55 False 4 1 56 False 3 1 57 False 9 3 58 False 3 1 59 True 1 1 60 False 27 3 61 True 1 1 62 False 3 1 63 False 9 3 64 False 43 1 65 False 16 1 66 False 45 3 67 True 1 1 68 False 27 1 69 False 9 3 70 False 13 1 71 True 1 1 72 False 27 3 73 True 1 1 74 False 3 1 75 False 69 3 76 False 27 1 77 False 25 1 78 False 9 3 79 True 1 1 80 False 27 1 81 False 0 3 82 False 3 1 83 True 1 1 84 False 75 3 85 False 81 1 86 False 3 1 87 False 9 3 88 False 75 1 89 True 1 1 90 False 63 3 91 False 1 1 92 False 27 1 93 False 9 3 94 False 3 1 95 False 24 1 96 False 75 3 97 True 1 1 98 False 59 1 99 False 27 3 100 False 67 1实验结果：对于n从2到100这么多数中，含有True的都为素数，而且对于这些素数，3（n-1）（除了素数3）被n整除所得余数都为1当m=4时的情况Mn_Integer:=Moduley,k,m=4;k=m(n-1);x=Modk,n; Printn, ,PrimeQn, ,x, ,GCDm,nDoMn,n,2,100 2 True 0 2 3 True 1 1 4 False 0 4 5 True 1 1 6 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 20 False 4 4 21 False 16 1 22 False 4 2 23 True 1 1 24 False 16 4 25 False 6 1 26 False 4 2 27 False 7 1 28 False 8 4 29 True 1 1 30 False 4 2 31 True 1 1 32 False 0 4 33 False 16 1 34 False 4 2 35 False 11 1 36 False 16 4 37 True 1 1 38 False 4 2 39 False 16 1 40 False 24 4 41 True 1 1 42 False 16 2 43 True 1 1 44 False 20 4 45 False 16 1 46 False 4 2 47 True 1 1 48 False 16 4 49 False 29 1 50 False 44 2 51 False 16 1 52 False 12 4 53 True 1 1 54 False 34 2 55 False 36 1 56 False 32 4 57 False 16 1 58 False 4 2 59 True 1 1 60 False 4 4 61 True 1 1 62 False 4 2 63 False 16 1 64 False 0 4 65 False 61 1 66 False 34 2 67 True 1 1 68 False 64 4 69 False 16 1 70 False 64 2 71 True 1 1 72 False 16 4 73 True 1 1 74 False 4 2 75 False 31 1 76 False 64 4 77 False 4 1 78 False 10 2 79 True 1 1 80 False 64 4 81 False 61 1 82 False 4 2 83 True 1 1 84 False 16 4 85 False 1 1 86 False 4 2 87 False 16 1 88 False 16 4 89 True 1 1 90 False 34 2 91 False 1 1 92 False 64 4 93 False 16 1 94 False 4 2 95 False 66 1 96 False 64 4 97 True 1 1 98 False 32 2 99 False 97 1 100 False 44 4实验结果：对于n从2到100这么多数中，含有True的都为素数，而且对于这些素数，4（n-1）（除了素数2）被n整除所得余数都为1当m=5时情况Mn_Integer:=Moduley,k,m=5;k=m(n-1);x=Modk,n; Printn, ,PrimeQn, ,x, ,GCDm,nDoMn,n,2,100 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 5 21 False 4 1 22 False 5 1 23 True 1 1 24 False 5 1 25 False 0 5 26 False 5 1 27 False 16 1 28 False 13 1 29 True 1 1 30 False 5 5 31 True 1 1 32 False 13 1 33 False 25 1 34 False 5 1 35 False 30 5 36 False 29 1 37 True 1 1 38 False 5 1 39 False 25 1 40 False 5 5 41 True 1 1 42 False 17 1 43 True 1 1 44 False 37 1 45 False 25 5 46 False 5 1 47 True 1 1 48 False 29 1 49 False 43 1 50 False 25 5 51 False 25 1 52 False 21 1 53 True 1 1 54 False 11 1 55 False 20 5 56 False 5 1 57 False 25 1 58 False 5 1 59 True 1 1 60 False 5 5 61 True 1 1 62 False 5 1 63 False 25 1 64 False 13 1 65 False 40 5 66 False 23 1 67 True 1 1 68 False 57 1 69 False 25 1 70 False 55 5 71 True 1 1 72 False 29 1 73 True 1 1 74 False 5 1 75 False 25 5 76 False 49 1 77 False 16 1 78 False 5 1 79 True 1 1 80 False 45 5 81 False 16 1 82 False 5 1 83 True 1 1 84 False 17 1 85 False 30 5 86 False 5 1 87 False 25 1 88 False 69 1 89 True 1 1 90 False 65 5 91 False 64 1 92 False 33 1 93 False 25 1 94 False 5 1 95 False 55 5 96 False 77 1 97 True 1 1 98 False 33 1 99 False 70 1 100 False 25 5实验结果：对于n从2到100这么多数中，含有True的都为素数，而且对于这些素数，5（n-1）（除了素数5）被n整除所得余数都为1实验小结：根据上述m取2,3,4,5进行实验，观察余数，得出以下结论 当m取偶数时，m（n-1）（除了素数2）被n整除所得余数为1 当m取奇数时，m（n-1）（除了素数m本身）被n整除所得余数为1 当n为素数时，程序里含有True练习二 素数的求解 Eratosthenes筛法Sieven_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!=0)&; t Sieve10000 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,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,