不大于某个数的最大素数

northwolves

设N为介于10^4-10^20间的某个整数,求不大于$sqrt(N/2)$的最大素数的高效方法

mathe

好好看看帖子
http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid10264
就可以了

northwolves

一年前曾经仔细看过,看来还需再次认真拜读,谢谢mathe
---------------------------------------

207#  发表于 2008-12-23 00:31 | 只看该作者
强帖留名。花了我近1个小时，累啊。

medie2005

miller-rabin算法判素。10^10内，素数基选(2,3,35543)就可以了。

KeyTo9_Fans

抛开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倍。