[已解决]梅森素数能用筛法求吗

额外减小

如题
不知道梅森素数能否用筛法来更快地求出。（只要unsigned long long 范围的就行。）
纯属萌新，大佬勿喷（）

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2023-3-4 08:20:17

或者你可用卢卡斯-莱默质数判定法：

#  Lucas–Lehmer primality test
def MersennePrimes(n):
        s = 4
        t = n - 2
        f = lambda s, M: ((s * s) - 2) % M
        M = (2 << (n - 1)) - 1
        res = None
        while t:
                t -= 1
                res = f(s, M)
                s = res
        return not res

print(MersennePrimes(11)) # M11 = 2047 不是梅森素数

False

跳转到最佳答案楼层

额外减小

就是说从素数里面能不能再进行一些筛选？

wp231957

额外减小 发表于 2023-3-2 23:44
就是说从素数里面能不能再进行一些筛选？

一共也没几个数   一个一个的试呗

额外减小

wp231957 发表于 2023-3-3 14:32
一共也没几个数   一个一个的试呗

噢，但这太慢了
我要求到第10个都得好几分钟
更别说后面的了
但如果后面没人回的话我就直接把你设最佳了

傻眼貓咪

梅森素数条件 = 梅森数 + 素数
梅森数是2次方-1，这个简单，因为没有几个数值就已经很大了
素數的部分你可以用平常的方式判斷是否是素數

傻眼貓咪

或者你可用卢卡斯-莱默质数判定法：

#  Lucas–Lehmer primality test
def MersennePrimes(n):
        s = 4
        t = n - 2
        f = lambda s, M: ((s * s) - 2) % M
        M = (2 << (n - 1)) - 1
        res = None
        while t:
                t -= 1
                res = f(s, M)
                s = res
        return not res

print(MersennePrimes(11)) # M11 = 2047 不是梅森素数

False

额外减小

傻眼貓咪 发表于 2023-3-4 08:20
或者你可用卢卡斯-莱默质数判定法：

好吧，谢谢你