寻找梅森质数应该先排除2^(2n)-1

tsyxzh

梅森质数就是2^n-1（注：^为指数格式表示，2^n表示2的n次方）型数中的质数，要从2^n-1型数中筛选出质数，应该先排除掉2^(2n)-1型数（2^2-1=3除外），只需再从2^(2n+1)-1型数中筛选，因为2^(2n)-1型数都是3的倍数。
证明：2^(2*1)-1=2^2-1=3，是3的倍数；
     2^(2n+2)-1=2^(2n)*4-1=(2^(2n)-1)*4+3，若2^(2n)-1是3的倍数，则2^(2n+2)-1也是3的倍数；
     由以上递推，所有2^(2n)-1型数都是3的倍数，其中仅2^2-1是3 的1倍，为质数。

tsyxzh

我想到了一种可以快速寻找大质数的方法，这种方法跟梅森质数相似的地方是也可以用较简单的方式表达（不过这个表达式比梅森数的表达式复杂一些），而且这种表达式的值中质数的比例比梅森数高，并且我也有判断这种数是不是质数的方法，不过对于很大的数，计算过程也只能交给电脑处理。我不知道判断一个梅森数是不是质数的方法是不是比较简单，所以我不知道我的方法是否可以更快找到比已知的最大质数更大的质数。
因为这种方法不是三言两语可以表达，而我现在工作实在太忙，没时间整理，所以今天没发，等过些天（最多一个月，争取一个星期内）我一定整理出来给大家看。今天886！

wreck

寻找梅森质数应该先排除2^(2n)-1
这个应该是已经被排除了的
GIMPS寻找时所有的2^p-1型数中p已经是素数了
事实上很容易证明，对所有合数m均有
2^m-1为合数

yutian

引用 wreck 在 2005-8-15 10:24 AM 时的帖子:
寻找梅森质数应该先排除2^(2n)-1
这个应该是已经被排除了的
GIMPS寻找时所有的2^p-1型数中p已经是素数了
事实上很容易证明，对所有合数m均有
2^m-1为合数

对了，早已经被证明了