素----数-数学实验报告.doc

素 数一、实验解读 德国数学家高斯说过，数学是科学的女王，而数论是数学的女王，在数论这一充满了趣味而布满荆棘的领域中，有关素数的问题，像著名的歌德巴赫猜想，始终是充满魅力和引人入胜的研究问题本实验将探讨素数的规律及相关的某些有趣问题，具体的说，我们将研究有关素数的下列问题：素数表的问题，分别用筛选法和试除法找出素数，比较两种方法的有效性并寻找素数的判别的公式，通过实验构造出通过素数生成公式观察素数的分布规律，利用不同基函数非线性拟合素数分布，验证和发现有关数论方面的结论二、实验方案1．素数的判别与求解 如果一个大于1的自然数只能被1及它的本身整除，则该数称为素数，否则称为合数欧几里得证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时，这样的分解时惟一的，这就是算术基本定理由此带来一个最基本的问题，素数到底有多少个，会不会在一个充分大的自然数以后就没有素数了呢？ 假设已知前n个素数，他们按从小到大的顺序排列为p1=2 p2=3，…,2O，计算Nn=p1p2…pn+1.Nn是否都是素数？如果Nn不是素数，Nn是否含有不同于pi的素因子将n从20开始增大，n=25,30,35…,观察结论变化。

并猜测素数是否有无穷多个？给出相关证明2.素数表的构造 关于素数的一个基本问题是：如何求出小于某一个给定整数的所有素数？为解决这一问题，我们提供两种方法，Eratosthenes筛法和试除法本实验通过两种方法进行有效性比较Eratosthenes筛法的基本思想：将自然数列从2开始按顺序排列至某一整数N首先，从上述数列中划除所有2的倍数（不包括2），在剩下的数列中，划掉所有3的倍数（不包括3），然后在剩下的数列中再划去5的倍数 ……这个过程一直进行下去，则最后剩下的数就是不超过N的所有素数借用Eratosthenes筛法，可以求出一定范围内的素数试除法：假设我们已经找到了前n个素数p1=2，p2=3，…,pn,为了寻找下一个素数从pn+2开始依次检验每一个整数N，看N是否能被某个pi（i=1,2,3,…n）整除如果N能被前面的某个素数整除，则N为合数，否则N即为下一个素数pn+1实际上，为了提高算法的效率，我们不需要前面的每一个素数去试除N，而只需要用不超过N^(1/2) 的素数去除就可以了分别用两种方法求出1000以内的素数，并比较两种方法的有效性将范围扩大，分别求出10000,100000，…,以内的素数，并比较两种方法的有效性。

3．素数的判别公式虽然从理论上说，利用Eratosthenes筛法和试除法可以求出所有的素数，但通过上面的实验可以发现，运用这些方法构造太大的素数不切实际本实验用Mathematica命令PowerMod[a,b,n]，表示a^b 被n整除的余数对n=2 ,3 ,…, 100中不同的数,观察m ^( n - 1)被n整除所得的余数取其他的整数m=2，m=3，m=4观察m^n-1被n整除的情况固定n的取值，变化m的值，那么我们得出的结果又会怎样？ 取n=2， m=2,3,……，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数，及形如2^n-1的数对n=2,3，….,300, 判断Mersenne数Mn=2^n-1是否是素数如果n为合数，Mersenne数是否是素数，n为素数，Mersenne数是否一定是素数？得出Mersenne数与n的关系，并证明。

4. 生成素数的公式是否存在一个生成素数的多变量函数公式？如果这样的公式不存在，能否找到一个虽不能给出全部但能给出无穷多个素数的公式Fermat函数：我们把形如+1表示出来的数称为Fermat数Fermat函数是否都是素数，增大n的值，可以发现Fn并不永远是素数验证当n=5,6,7,8,9,10时，Fermat函数Fn均为合数单变量的整数系多项式：形如n^2+n+41对n=0, 1, …100,计算n^2+n+41.他们是否都是素数类似的，对公式n^2-79n+1601及6n^2+6n+31做同样的判别能否给出一个类似的公式5. 素数的分布如果你将素数在数轴上标出来，会发现素数的分布很不规则，通过本实验做进一步的观察Mathematica命令PrimePi[n]给出所有小于等于n的素数的个数用表示不超过n 的素数的个数，表示区间 [m,n] 内素数的个数，再计算﹑﹑以及﹑﹑﹑从计算结果看，随着范围的扩大，素数是越来越稀还是越来越密？进一步，选取一些更长的区间，再尝试以上同样的实验将这些点画在图中，从图中能更清晰的看出素数的分布情况将素数按从小到大的顺序排列，p1=2，p2=3，… ,用dn=pn+1 – pn表示相邻的素数间的间隔。

计算d1，d2，… dn，然后将点（pn，dn）表示在平面坐标系中从中观察素数间隔的规律如素数的间隔值有哪些，他们个重复多少次，最大间隔值是多少，增大n的值，最大间隔值是否也随之增大6. 用函数对素数的个数进行拟合 用函数对素数的个数进行拟合先进行线性拟合，选取2到1000中所有的素数进行拟合，再改变拟合的多项式的次数，比较拟合效果 将点（n, ）标在平面坐标系中,并且用折线把这些点连接起来，观察的变化趋势，然后在程序中增大N 的值，再观察的变化趋势，将的值与其它函数的值进行比较，看能否找出最接近的值的函数，即计算素数个数的公式，注意此时n应该充分大三．实验过程1素数的无穷性假设已知前n个素数，它们从小到大的顺序排列为p1=2,p2=3, … ,pn，对n=1，2，… ，20，计算Nn=p1p2 … pn+1，问：（1）Nn是否都是素数？ （2）如果Nn不是素数，Nn是否含有不同与pi（i=1，2，…，n）的素因子Mathematic程序如下：25程序运行结果如下：Mathematic³ÌÐòÈçÏ£º 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 False {{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}} False {{1063,1},{303049,1},{598841,1},{2892214489673,1}}由实验结果可得，Nn并非都是素数，当n>4时，Nn都是合数，但都可以写成几个素因子的乘积的形式。

继续增大n的值可以发现：N=25时 mathematics程序如下NumP[n_Integer]:= Module[{i,Num}, Num=Product[Prime[i],{i,1,n}]+1; Print[Num," ",PrimeQ[Num]," ",FactorInteger[Num] ]] Do[NumP[n],{n,20,25}]运行结果如下：从上可以看出，当n增大时，Nn虽然不是素数，但仍可以表示为几个素因子乘积的形式还可以发现，最大素因子的值呈增大趋势可以判断，因为Nn可以取无穷，并且如果Nn都可以用几个素因子乘积的形式表示的话，最大素因子的值也是无穷的，也即素数是无穷的2.素数表的构造Eratosthenes筛法：用Eratosthenes筛法求1000以内的素数程序如下：Sieve[n_Integer]:= Module[ {t={},i,temp}, For[i=2,i<=n,i++,AppendTo[t,i]]; For[i=1,Prime[i]<=Sqrt[n],i++,temp=Prime[i]; t=Select[t,(#1==temp||Mod[#1,temp]!=0)&]]; t] Sieve[1000]运行结果如下：{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,919,929,937,941,947,953,967,971,977,983,991,997}同样用试除法求1000以内的素数程序如下：DivPrime[n_Integer]:= Module[ {t={},i,j,temp,divided}, For[i=2,i<=n,i++, j=1;divided=False; While[Prime[j]<=Sqrt[i]&&(!divided), temp=Prime[j]; divided=(Mod[i,temp]==0);j=j+1]; 。