不大于某个数的最大素数
设N为介于10^4-10^20间的某个整数,求不大于$sqrt(N/2)$的最大素数的高效方法 好好看看帖子http://bbs.emath.ac.cn/viewthread.php?tid=803&page=1&fromuid=20#pid10264
就可以了 一年前曾经仔细看过,看来还需再次认真拜读,谢谢mathe
---------------------------------------
207#发表于 2008-12-23 00:31 | 只看该作者
强帖留名。花了我近1个小时，累啊。 miller-rabin算法判素。10^10内，素数基选(2,3,35543)就可以了。 抛开miller-rabin不提，尝试筛法。
$sqrt(N/2)<7071067812$
$sqrt(7071067812)<84090$
2到84090之间的素数有8198个。
把这些素数记下。
1到7071067812的最大素数间隔大概是350吧？
为了保险起见，当它是400好了。
在查询的数前面铺一块400米长的地毯。
根据地毯的位置对8198个素数的余数，就知道这些素数会把地毯上的哪些地方挖掉。
再看看查询的数前面最近的没挖掉的地方，就是所要求的最大素数。
其实和分段筛法的原理是一样的。
说白了也就是在一段长度为400的地毯上用8198个素数作筛法。
筛好了结果就出来了。
用了8198次mod运算和少量的加法运算。
而平均情况下，查询的数前面12米的地方就是答案。
用miller-rabin判6个奇数即可。
所以如果miller-rabin判一个数可以在1366次运算之内完成，那么还是miller-rabin快。
而实际上用3组素数基一共只需100次运算左右吧？
所以如果会miller-rabin的话，还是用miller-rabin的好，比筛法快10倍。
页:
[1]