c - 检查一个数字是否是没有筛子的素数

Question

所以我需要解决一个问题，找到验证以下内容的第 n 个数：它是两个连续素数的和，它给出一个整数平方根。我的问题是，eratosthenes 的筛子使用了太多的内存，而对素数的天真检查太慢了。有什么方法可以快速解决这个问题并且没有额外的记忆？我尝试使用费马定理，但结果速度较慢。

提前致谢。

Answer 1

您可以使用 Rabin-Miller 进行素性测试。它是概率性的，所以它只告诉你一个数字可能是素数，但你可以设置确定性的水平。它非常快，并且对内存的要求很低。

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