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

额外减小

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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2023-3-4 08:20:17

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

1. #  Lucas–Lehmer primality test
   
2. def MersennePrimes(n):
   
3.         s = 4
   
4.         t = n - 2
   
5.         f = lambda s, M: ((s * s) - 2) % M
   
6.         M = (2 << (n - 1)) - 1
   
7.         res = None
   
8.         while t:
   
9.                 t -= 1
   
10.                 res = f(s, M)
    
11.                 s = res
    
12.         return not res
    
13. 
    
14. print(MersennePrimes(11)) # M11 = 2047 不是梅森素数

复制代码

1. False

复制代码

跳转到最佳答案楼层

额外减小

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

wp231957

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

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

额外减小

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

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

傻眼貓咪

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

傻眼貓咪

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

1. #  Lucas–Lehmer primality test
   
2. def MersennePrimes(n):
   
3.         s = 4
   
4.         t = n - 2
   
5.         f = lambda s, M: ((s * s) - 2) % M
   
6.         M = (2 << (n - 1)) - 1
   
7.         res = None
   
8.         while t:
   
9.                 t -= 1
   
10.                 res = f(s, M)
    
11.                 s = res
    
12.         return not res
    
13. 
    
14. print(MersennePrimes(11)) # M11 = 2047 不是梅森素数

复制代码

1. False

复制代码

额外减小

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

好吧，谢谢你