探索实验之素数.docVIP

数学探索实验 （素数） 姓 名： 欧荣军 班 级： 数学081 学 号： 0802012038 指导教师： 林道荣 完成日期： 2010-11-20 素数 实验指导书解读 德国数学家Gauss说过，数学是科学之王，而数论则是数学的女王。从数学史的黎明时期开始，数学家们就一直在探索自然数的奥秘，而在数论这一充满了趣味而布满荆棘的领域中，有关素数的问题（如著名的Goldbach猜想）始终是最富有魅力、最吸引人的研究问题。 本文主要研究素数的无穷性以及素数的一些规律。首先，借助素数的定义，即如果一个大于1的自然数只能被1及它本身整除，则该数为素数，通过前n个素数来研究素数的无穷多性，并利用Eratosthenes筛法和试除法来构造某一给定自然数以内的素数表，利用算法比较这两种方法的有效性，并进而研究大素数的生成情况。进一步为了研究素数的判别，我们给出了一些幂指数形式的数，接着对Mersenne数进行研究，判别Mersenne数是否全是素数，从中给出素数判别的方法，然后我们利用Fermat数，Euler数的素性规律来研究是否存在生成素数的公式以及这些公式的基本形式（比如单变量的整系数多项式函数、多变量的整系数多项式函数等），通过观察这些公式生成素数的个数，寻找素数生成公式，最后运用非线性拟合方法来研究素数个数的分布规律（比如不同区间范围内素数的个数、相邻素数的差值大小等等），并给出素数个数的近似公式。 实验计划 素数的无穷性 远在古希腊时代，Euclid就证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序是这种分解是唯一的，这就是著名的算术基本定理。它表明，素数是构造自然熟的基石，正如物质的基本粒子一样。首先，一个最基本的问题是：素数到底有多少个？会不会在某一充分大的自然数之后就没有素数呢？先做以下实验： 1．1 实验1 判断前n个素数相乘后再加1所得的数是否还构成素数的Mathematica程序 NumP[n_Integer]:= Module[{i,Num}, Num=Product[Prime[i],{i,1,n}]+1; Print[n, ,Num, ,PrimeQ[ Num], ,FactorInteger[Num]]] Do[NumP[n],{n,1,20}] 1．2 实验思路： 计算（其中为前n个素数）的数值，判断当n=1，2，3……时是否为素数。 若不是素数，即是合数，判别是否含有不同于（i=1，2，3……,n）的素因子。 1．3 实验思考： 根据实验1的结果，分析并猜测素数是否有无穷多个？试给出证明。 素数表的构造 根据实验1的结论：素数是有无穷多的，我们可以知道小于某一给定整数的所有素数是可以求出的，以下我们利用Eratosthenes筛法和试除法来构造某一整数内的素数表。 2．1 实验2 Eratosthenes 筛法的基本思想：将自然数列从2开始按顺序排列之某一整数N，首先从上述数列中划除所有2的倍数（不包括2），在剩下的数中，除2外最小的是3，接着，从数列中划掉所有3的倍数（不包括3），然后在剩下的数中，再划去所有5的倍数……这个过程一直进行下去，则最后剩下的数就是不超过N的所有素数。 试除法的基本思想：假设我们已经找到了前n个素数，，，，为了寻找下一个素数我们从+2开始依次检验每一个整数N，看N是否能被某个（i=1,2,……,n）整除，如果N能被前面的某个素数整除，则N为合数；否则N即为下一个素数。 2．2 实验程序 Eratosthenes筛法程序： 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] 试除法程序： 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]; divide