灵鹊做题网ACM数论 梅森素数检测问题
来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：数学作业 时间：2024/05/05 22:39:14
ACM数论 梅森素数检测问题
如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.
现给出一个整数p（1
如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.
现给出一个整数p（1
刚在wiki上看到梅森素数的这个判断性质：
Mn为素数当且仅当Mn整除Sn-2（S0=4,S(k) = S（k − 1）^2 − 2,k > 0）.
用这个将使得复杂度由O(n)降到O(logn)
参考资料：
http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0
再问： 那个卢卡斯定理就是楼上说的那个定理吧，但是在这道题上面这个定理我感觉用不了；至于下面那个完全数结论我也想过但是也没什么想法。
不过还是多谢了！
再答： 我不是搞计算的，不过我有一些想法你看看是否可行：
要考虑M(p)是不是素数，可以考虑对小于2^(p-1)的素数q进行验证,如果M(p)不是素数，则存在q:
M(p)=0 mod q 2^p=1 mod q (1)
于是有q-1=pk.即q=pk+1.
就是说我们把判断M(p)
是不是素数转化为判断(1)是不是错的.
再看看q=pk+12^(p-1)时,则表明M(p)是素数.
当然，你可以考虑对pk+1是不是素数进行判定，如果在算数级数pk+1在小于2^(p-1)里面都没有素数，那么显然M(p)是素数(当然，这个似乎有定理(或是猜想)说明pk+1
Mn为素数当且仅当Mn整除Sn-2（S0=4,S(k) = S（k − 1）^2 − 2,k > 0）.
用这个将使得复杂度由O(n)降到O(logn)
参考资料：
http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0
再问： 那个卢卡斯定理就是楼上说的那个定理吧，但是在这道题上面这个定理我感觉用不了；至于下面那个完全数结论我也想过但是也没什么想法。
不过还是多谢了！
再答： 我不是搞计算的，不过我有一些想法你看看是否可行：
要考虑M(p)是不是素数，可以考虑对小于2^(p-1)的素数q进行验证,如果M(p)不是素数，则存在q:
M(p)=0 mod q 2^p=1 mod q (1)
于是有q-1=pk.即q=pk+1.
就是说我们把判断M(p)
是不是素数转化为判断(1)是不是错的.
再看看q=pk+12^(p-1)时,则表明M(p)是素数.
当然，你可以考虑对pk+1是不是素数进行判定，如果在算数级数pk+1在小于2^(p-1)里面都没有素数，那么显然M(p)是素数(当然，这个似乎有定理(或是猜想)说明pk+1