素数实验报告

1、精选优质文档-倾情为你奉上素 数一实验解读如果一个大于1 的自然数只能被1及它本身整除，则称该数为素数，否则称为合数。每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时这种分解是唯一的，这就是所谓的算术基本定理。Mersenne数与Fermat数是两种具有特殊结构的数。Mn=2n-1，Fn=2(2n)+1。如果将素数在数轴上标出来，会发现素数的分布很不规则。我们需做实验进一步观察随着整数范围的扩大，素数是越来越稀还是越来越密？关于素数还存在许许多多富于挑战性的问题，如猜想；大整数的素因子分解；完全数；孪生素数猜想；青一色数的素数二实验思路 1.素数的判别与个数 在大于1的自然数

2、中，只能被1和它本身整除的数称为素数。 规定Nn=p1p2.pn+1，当n=1,.,20时判断Nn是否是素数，如果不是，那么Nn能不能表示成几个素因子相乘的形式。 改变n的取值范围，观察得出结论。 根据以上的结果，猜测素数是否有无穷多个，并给出相关的证明。2素数表的构造 用Eratosthenes筛法和试除法列出1000内所有的素数，比较哪种方法所用的时间比较少。它们的原理为： Eratosthenes筛法的基本原理，将自然数列从2开始按顺序排列至某一整数N，首先，从上述数列中划除所有2的倍数（不包括2），在剩下的数中，除2外最小的是3.接着，从数列中划除所有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，1

4、00取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数的素性判别： 形如2n-1的数称为Mersenne数，通过Mersenne数我们可以研究数论中的相关性质。观察并考

5、虑Mersenne数与n的关系，得出一般性的结论，4.生成素数的公式Fermat数：我们把形如+1表示出来的数称为Fermat数。Fermat数是否都是素数？在程序中增大n的值，很容易知道当n变大到一个特定的值时，Fermat数不再是素数。 既然Fermat数不能作为素数的生成公式，那么能不能寻求一个整系数单变量多项式，使得它能生出所有的素数。首先考虑一次函数，显然是不行的。再考虑二次多项式，如：f(n)=+n+41，f(n)=-79n+1061，f(n)=6+6n+31，观察是否无论n如何变化，f(n)都是素数。若不是，再改变多项式的次数，观察得出的结果有什么不同。 若单变量整系数多项式不能

6、生成所有的素数，那么多变量整系数多项式呢？ 判断以上的f(n ,m)是否生成的均是素数，它们之间有什么规律？5.素数的分布在上面的实验中我们已经知道了素数是无穷多个的，而且素数的生成公式并不是很明了，但是它的分布会不会具有什么样的规律呢？ 实验中，用表示不超过n 的素数的个数，表示区间 m,n 内素数的个数，再计算以及。从计算结果看，随着范围的扩大，素数是越来越稀还是越来越密？进一步，选取一些更长的区间，做同样的实验。将这些点画在图中，从图中能更清晰的看出素数的分布情况。换一个角度考虑，从两个相邻素数间距的大小同样也可以看出素数的分布，这时我们还可以发现一些更有趣的规律。先求出1000以内的所

7、有相邻素数的间距，并将点以（，）的形式画在直角坐标系中，观察图像的特点；增大n的值，再在另一个图中画出，从这些点的分布可以看出素数的间隔值的某些特征，以及它们的重复次数的多少，我们还发现：在增大N的值的同时，图中的点也会随之变高，也就是说最大间隔值在变化。 6. 用函数对素数的个数进行拟合 用函数对素数的个数进行拟合。先进行线性拟合，选取2到1000中所有的素数进行拟合，再改变拟合的多项式的次数，比较拟合效果。 将点（n, ）标在平面坐标系中,并且用折线把这些点连接起来，观察的变化趋势，然后在程序中增大N 的值，再观察的变化趋势，将的值与其它函数的值进行比较，看能否找出最接近的值的函数，即计算

8、素数个数的公式，注意此时n应该充分大。三实验过程与实验结果1素数的无穷性假设已知前n个素数，它们从小到大的顺序排列为p1=2,p2=3,.,pn，对n=1，2，20，计算Nn=p1p2pn+1，问： （1）Nn是否都是素数？ （2）如果Nn不是素数，Nn是否含有不同与pi（i=1，2，n）的素因子？Mathematic程序如下：NumPn_Integer:= Modulei,Num, Num=ProductPrimei,i,1,n+1; PrintNum," ",PrimeQNum," ",FactorIntegerNum DoNumPn,n,1,20

9、实验结果： 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 False 19,1,97,1,277,1 False 347,1,27953,1 False 317,1,1 False 331,1,571,1,34231,1 1 True 1,1 11 False 181,1,60611,1,1 7211 False 61,1,1,1 False 167,1,593,1 False 953,1,46727,1,1 False 73,1,139,1,173,1,301

10、,1 False 277,1,3467,1,1,1 71 False 223,1,1 091 False ,1,9603,1 15391 False 1063,1,1,1,73,1由此可以看出并不是所有的 Nn=p1p2pn+1都是素数，但是所得出的合数都能表示成若干个素数相乘的形式，与算术基本定理相符合。根据以上的结果我们可以得出素数是间隔着出现的，两个连续素数间间隔的合数个数也是不确定的，我们就有这样的疑问：素数的个数是否是无穷的？当n=20,21,.25，程序与结果如下： NumPn_Integer:= Modulei,Num, Num=ProctPrimei,i,1,n+1; Prin

11、tn," ",Num," ",PrimeQ Num," ",FactorIntegerNum DoNumPn,n,20,25 20 15391 False 1063,1,1,1,73,1 21 False 2521,1,6951,1 22 False 22093,1,1,1 23 False ,1,1 24 11 False 131,1,1039,1,2719,1,6141,1 25 6071 False ,1,1,9,1当n=25,.30，输出结果为： 25 6071 False ,1,1,9,1 26 False ,1,1 27

12、False 2297,1,1,7,1,34531,1 28 False 149,1,1,1,1 29 1 False ,1,1,1 30 991 False ,1,07,1,1根据上面的结果，很容易看出，虽然n不全是素数，但分解出的素因子在不断变大。由此，我们可假设命题：素数的个数是无穷多个的。 证明：反证法，若素数的个数是有限的，且最大的素数是pk。令N=p1p2.pk+1，N>pk，则N是合数，根据算术基本定理，N存在素因 子p，则 可得出pp1p2.pk，且pN p1，这与p是素数相矛盾。 故而假设不成立。 得证：素数的个数是无穷多个的。2.Eratosthenes筛法与试除法通过

13、Eratosthenes筛法求1000以内的素数并计时，程序如下： 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 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

14、,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

15、,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,997 Sieven_Integer:= Module t=,i,temp, Fori=2,i<=n,i+,AppendTot,

16、i; Fori=1,Primei<=Sqrtn,i+,temp=Primei; t=Selectt,(#1=temp|Mod#1,temp!=0)& TimingSieve1000 实验结果：0.031 Second,Null即用Eratosthenes筛法求1000以内的素数所用的时间是0.031。用试除法求1000以内的素数并计时，程序如下： DivPrimen_Integer:= Module t=,i,j,temp,divided, Fori=2,i<=n,i+, j=1;divided=False; WhilePrimej<=Sqrti&&(

17、!divided), temp=Primej; divided=(Modi,temp=0);j=j+1; If!divided,AppendTot,i; t DivPrime1000 实验结果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,2

18、77,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,7

19、57,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,997 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=

20、0);j=j+1; If!divided,AppendTot,i;TimingDivPrime1000 实验结果：0.157 Second,Null即用试除法求1000以内的素数所用的时间是0.157由以上程序的结果可得，Eratosthenes筛法比试除法的时间要快，故而可得Eratosthenes筛法比试除法要好3.素数的判别公式 对n=2 ,3 , 100,观察m （n - 1)被n整除所得的余数. 当m=2时 运行如下程序：. Mn_Integer:=Moduley,k,m=2;k=m(n-1);x=Modk,n; Printn," ",PrimeQn,"

21、 ",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 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 Fals

22、e 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 3

23、1 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 Fals

24、e 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

25、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为素数时，2n-1被n整除所得的余数都是1。 那么，再取其他的整数m=3, 观察3 (n - 1)被n整除所得的余数. 运行如下程序: Mn_Integer:=Moduley,k,m=3;k=m(n-1);x=Modk,n; Printn," ",PrimeQn," "

26、,GCDm,n," ",x DoMn,n,2,100实验结果： 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

27、23 True 1 1 24 False 3 3 25 False 1 6 26 False 1 3 27 False 3 0 28 False 1 27 29 True 1 1 30 False 3 3 31 True 1 1 32 False 1 11 33 False 3 9 34 False 1 3 35 False 1 4 36 False 3 27 37 True 1 1 38 False 1 3 39 False 3 9 40 False 1 27 41 True 1 1 42 False 3 33 43 True 1 1 44 False 1 27 45 False 3 36

28、46 False 1 3 47 True 1 1 48 False 3 27 49 False 1 43 50 False 1 33 51 False 3 9 52 False 1 27 53 True 1 1 54 False 3 27 55 False 1 4 56 False 1 3 57 False 3 9 58 False 1 3 59 True 1 1 60 False 3 27 61 True 1 1 62 False 1 3 63 False 3 9 64 False 1 43 65 False 1 16 66 False 3 45 67 True 1 1 68 False 1

29、 27 69 False 3 9 70 False 1 13 71 True 1 1 72 False 3 27 73 True 1 1 74 False 1 3 75 False 3 69 76 False 1 27 77 False 1 25 78 False 3 9 79 True 1 1 80 False 1 27 81 False 3 0 82 False 1 3 83 True 1 1 84 False 3 75 85 False 1 81 86 False 1 3 87 False 3 9 88 False 1 75 89 True 1 1 90 False 3 63 91 Fa

30、lse 1 1 92 False 1 27 93 False 3 9 94 False 1 3 95 False 1 24 96 False 3 75 97 True 1 1 98 False 1 59 99 False 3 27 100 False 1 67从运行结果可以发现: 当n(除3以外)为素数时，3 ( n 1)被n整除所得的余数都是1。类似地, 令m=4，实验结果： 2 True 2 0 3 True 1 1 4 False 4 0 5 True 1 1 6 False 2 4 7 True 1 1 8 False 4 0 9 False 1 7 10 False 2 4 11 T

31、rue 1 1 12 False 4 4 13 True 1 1 14 False 2 4 15 False 1 1 16 False 4 0 17 True 1 1 18 False 2 16 19 True 1 1 20 False 4 4 21 False 1 16 22 False 2 4 23 True 1 1 24 False 4 16 25 False 1 6 26 False 2 4 27 False 1 7 28 False 4 8 29 True 1 1 30 False 2 4 31 True 1 1 32 False 4 0 33 False 1 16 34 False

32、 2 4 35 False 1 11 36 False 4 16 37 True 1 1 38 False 2 4 39 False 1 16 40 False 4 24 41 True 1 1 42 False 2 16 43 True 1 1 44 False 4 20 45 False 1 16 46 False 2 4 47 True 1 1 48 False 4 16 49 False 1 29 50 False 2 44 51 False 1 16 52 False 4 12 53 True 1 1 54 False 2 34 55 False 1 36 56 False 4 32

33、 57 False 1 16 58 False 2 4 59 True 1 1 60 False 4 4 61 True 1 1 62 False 2 4 63 False 1 16 64 False 4 0 65 False 1 61 66 False 2 34 67 True 1 1 68 False 4 64 69 False 1 16 70 False 2 64 71 True 1 1 72 False 4 16 73 True 1 1 74 False 2 4 75 False 1 31 76 False 4 64 77 False 1 4 78 False 2 10 79 True

34、 1 1 80 False 4 64 81 False 1 61 82 False 2 4 83 True 1 1 84 False 4 16 85 False 1 1 86 False 2 4 87 False 1 16 88 False 4 16 89 True 1 1 90 False 2 34 91 False 1 1 92 False 4 64 93 False 1 16 94 False 2 4 95 False 1 66 96 False 4 64 97 True 1 1 98 False 2 32 99 False 1 97 100 False 4 4以上我们考虑的是m固定，变

35、化n的情况，接下来分析一下n固定，变化m的情况。n=2,m=2,3,100程序如下 Mm_Integer:=Moduley,k,n=2;k=m(n-1);x=Modk,n; Printm," ",PrimeQm," ",GCDm,n," ",x DoMm,m,2,100实验结果： 2 True 2 0 3 True 1 1 4 False 2 0 5 True 1 1 6 False 2 0 7 True 1 1 8 False 2 0 9 False 1 1 10 False 2 0 11 True 1 1 12 False 2 0

36、 13 True 1 1 14 False 2 0 15 False 1 1 16 False 2 0 17 True 1 1 18 False 2 0 19 True 1 1 20 False 2 0 21 False 1 1 22 False 2 0 23 True 1 1 24 False 2 0 25 False 1 1 26 False 2 0 27 False 1 1 28 False 2 0 29 True 1 1 30 False 2 0 31 True 1 1 32 False 2 0 33 False 1 1 34 False 2 0 35 False 1 1 36 False 2 0 37 True 1 1 38 False 2 0 39 False 1 1 40 False 2 0 41 True 1 1 42 False 2 0 43 True 1 1 44 False 2 0 45 False 1 1 46 False 2 0 47 True 1 1 48 False 2 0 49 False 1 1 50 False 2 0 51 False 1 1 52 False 2 0 53 True 1 1 54 False 2 0 55 False 1 1 56 False 2 0 57 False 1 1