找回密码
 新注册用户
搜索
查看: 11330|回复: 5

[求助] 用素数筛找最大素数烦不烦

[复制链接]
发表于 2009-2-16 20:36:47 | 显示全部楼层 |阅读模式
寻找素数,还可以使用素数筛,即把一定范围内的素数的倍数去掉,即把合数去掉,剩下的都是素数,
轻问如果用这种方法找梅森素数,方法简便不,谢谢。
回复

使用道具 举报

发表于 2009-2-23 17:44:21 | 显示全部楼层

当然不简便

这样需要极大的存储空间(1亿位梅森素数就需要1亿*10^1亿+1000万*10^1000万……字节)
而且梅森数(符合2^p-1的数)微乎其微,所以这样完全不必要,且效率极其低下
回复

使用道具 举报

发表于 2009-5-10 10:13:07 | 显示全部楼层
要判断的话,我宁可用Rabin-Miller
回复

使用道具 举报

发表于 2009-6-11 19:20:08 | 显示全部楼层
对于梅森素数的素性判断来说 Rabin-Miller 算法的效率并不比 Prime95(GIMPS) 用的卢卡斯-莱默测试(Lucas-Lehmer testing)高多少, 说不定还会更慢些.
Rabin-Miller 中关键一步是判断 a^((m - 1)/2) = 1 (mod m)
其中 m = 2^p - 1 为待验证的梅森数, a 是随机选的一个数. 需要计算 log2((m - 1)/2) ≈ p-1 次模乘法.
而卢卡斯-莱默测试需要计算 p-2 次 型如 (S^2 - 2) mod m 的模乘法....
更关键的, Rabin-Miller 不能确定一个数的素性, 多次测试测试的话效率就更低了.

参考:
Rabin-Miller Strong Pseudoprime Test
http://mathworld.wolfram.com/Rab ... seudoprimeTest.html
Prime95(GIMPS) 用的卢卡斯-莱默测试(Lucas-Lehmer testing)
http://www.equn.com/gimps/math.htm
回复

使用道具 举报

发表于 2009-9-3 18:20:23 | 显示全部楼层
更关键的, Rabin-Miller 不能确定一个数的素性, 多次测试测试的话效率就更低了.

正解……
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 新注册用户

本版积分规则

论坛官方淘宝店开业啦~

Archiver|手机版|小黑屋|中国分布式计算总站 ( 沪ICP备05042587号 )

GMT+8, 2024-3-29 18:53

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表