梅森素数.doc

梅森素数S0FAREDEVEL0PMENTANDDESIGN软件开发与设计梅森素数刘建波,陈杰,王硕(东北大学秦皇岛分校电子信息系,秦皇岛066004)摘要:梅森素数是数论研究中的一项重要内容,,定理,算法和意义,:素数;梅森素数;数论;C语言;GIMPSMersennePrimeLIUJianbo-(NortheasternUniversityatQinhuangdao,DepartmentofElectronicInformation,Qinhuangdao066004)Abstract:Mersenneprimeisanimportantscientificexplorationofthestudyofnumbertheory,,introducedtherelevantdefinitions,theorems,algorithmsandmeaning,anddis-:prime;Memenneprime;Numbertheory;Clanguage;GIMPS1引言素数又称质数,是只能被1和其自身整除的自然数,如2,3,5,7,(其中P为素数),则2p一1称为梅森素数(MersennePrime),,定理【l_:n是偶完全数的充分必要条件是n=2p一1?(2p一1),(Euclid)证明了若P与2p一1都为素数,则2p一1(2p一1)为一偶完全数;欧拉(Euler),,研究梅森素数具有重大的意义:传承数学文明,感受数学之美,挑战人类计算智力极限,推动了数学皇后一数论的研究,测试硬件,计算机通信消息的加密和解密,,,中国数学家及语言学家周海中提出了着名的"周氏猜想".GIMPS是一个全球性的利用网格技术搜索梅森素数的计划[(EFF)于1999年向全世界宣布::超过1亿位数,15万美元;超过l0亿位数,,科学界对梅森素数非常重视,迄今为止,,大家只要学过编程都能看懂,即使是初学者也能感受到利用简单程序解决世界着名问题的乐趣,,:2009—9—20(1):给定一个数n,用小于等于的?n每个数去试除n,如果能找到因子,则n是合数;,任意给定一个素数P,可以用试除法判断Mp=2p一1是否为梅森素数,程序如下:衔nclude<>#include<math-h>voidmain0{intnumber=0,P=0,J=0;scanf("%dt',&p);,丰输入指数p/number=(int)pow(2,P)一l;intNUMBER=(int)sqrt(number);for(inti=2;i<=NUMBER;i+十){判断Mp=2P-1是否为素数/if(number%i==01f,木能被i整除,则Mp=2P-1不是素数,J--0;break;/*找到一个因子则可退出循环/)elsej=1;)if(J)prinff("P为%d时是梅森素数,Il",p);elseprinff("P为%d时不是梅森素数\n",p);J(2)某种意义上说,试除法是个效率非常低的算法,如果n有大小接近的素因子,,当n有至少一个小因子,,对于随机的n,2是其因子的概率是50%,3是33%,等等,88%的正整数有小于100的因子,91%的有小一41—.(1)列出如下这样以2开头的序列:2345678910lll2l3l415l61718l9202122232425(2)标出序列中