不大于某个数的最大素数

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