不用筛子检查一个数是否是素数

Question

关闭。这个问题需要更多 focused 。目前不接受答案。

---

想要改进这个问题吗？更新问题，使其仅关注 editing this post 的一个问题。

已关闭 8 年前。

奥 git _a

所以我需要解决一个问题，找到第n个数字来验证以下内容:它是两个连续素数的和，并且给出一个整数平方根。我的问题是埃拉托斯特尼筛使用了太多内存，而对素数的简单检查太慢。有什么方法可以快速解决这个问题并且不需要额外的内存？我尝试使用费马定理，但结果比较慢。

提前致谢。

Answer 1

您可以使用 Rabin-Miller 进行素性测试。它是概率性的，因此它仅告诉您某个数字可能是素数，但您可以设置确定性级别。它速度非常快，并且内存要求低。

显然，您只需要考虑偶数的平方，因为只有偶数可以是两个素数之和(一旦超过 2)。