数论吧 关注:13,748贴子:77,863
  • 0回复贴,共1

梅森素数编选法

只看楼主收藏回复

梅森素数编选法根据素数作为因子数在2^N-1数列中的分布规律而编选梅森素数。一 在2^N-1平方根以内没有奇素数的,这个指数的数就是梅森素数,后面的指数能被这个梅森素数整除的都有这个梅森素数的因子,周期重复的都编上这个因子数。二 在2^N-1数列中N是合数的,2^N-1是由前面素因子和新增的因子数组成,只要除去前面的因子数就能得到新的因子数,新的因子数也以这个指数为周期重复出现,并在后面重复的数编上这个因子数。三 指数是素数的,剩下的因子素数根据减1能被指数整除来选合,选合后并在后面的周期重复的数编上这些因子数;剩下的因子素数在2^N-1平方根以内选完后,还有梅森数空着,这个梅森数就是梅森素数,并在后面周期重复的数编上为些因子数。根据以上的方法操作如下:把2^n-1的指数都展开,从2开始编下去。指数2的数值是3,3的平方根内没有奇素数,所以它是梅森素数,凡是指数能被2整除的都有3的因子数,后面以2为周期编上因子数3;指数3的数值是7,7的平方根内没有奇素数,所以它也是梅森素数;凡是指数能被3整除的都有7的因子数,以3为周期编上因子数7;指数4数值是15,4能被2整除所以有3的因子数,15除以3等于5,5是新出现的因子数,凡是指数能被4整除的,都有5的因子数,后面以4为周期编上因子数5;指数是5数值是31,31的平方根以内只有3和5两个奇素数,3和5已是指数2和4的因子数了,所以这个梅森数是梅森素数,凡是指数能被5整除的,都有31的因子数,后面以5为周期编上因子数31;指数6数值是63,6比较特别,凡是指数能被6整除的都会再增一个3的因子数,它是唯一一个不会新增其他因子数的数,后面以6为周期再编上一个因子数3;指数7数值是127,127的平方根以内只有奇素数11还没有用上(实际以后都会用上的),11减1不能被7整除,所以127也是梅森素数,凡是指数能被7整除的都有127的因子数,后面以7为周期编上因子数127;指数8数值是255,增加了17的因子数,凡是指数能被8整除的都有17的因子数,后面以8为周期编上因子数17;指数9数值是511,新增73的因子数,凡是指数能被9整除的都有73的因子数,后面以9为周期编上因子数73;指数10数值是1023,新增11的因子数,凡是指数能被10整除的都有11的因子数,后面以10为周期编上因子数11;指数11数值是2047,2047的平方根内还有43,41,37,29,23,19,13等奇素数(只要往后多编一些,留下的数就更少了),只要将这几个数都减去1,那一个数被11整除,只有23-1能被11整除,2047/23=89,23和89是它的因子数,两个因子数都是新增加的,因为它是梅森合数,凡是指数能被11整除的都有23和89的因子数,后面以11为周期编上因子数23和89;指数12数值是4095,已有的因子数3*7*5*3,新的因子数是13,凡是后面指能被12整除的,都编上因子数13。指数13数值是8191,8191的平方根内还有83,79,73,71,67,61,59,53,47,43,41,29,19等素数,其中只有79-1能被13整除,用79试除也是不行,所以8191也梅森素数。一直编下去,每一个指数至少都会新增一个素数的因子数,不是梅森素数和梅森合数的因子数都能编选出来,没有选到的就是梅森合数的因子数和梅森素数。编梅森数时,根据素数减1能被指数整除的定理,从剩下素数中选合。2^N-1的平方根以内的素数都被因子数选完,留下就是梅森素数了。


IP属地:浙江1楼2020-11-30 10:21回复