我想计算一个数字以下的素数。如何有效地做到这一点。
我使用了埃拉托色尼筛，但它失败了，因为我的数字在 10^20 范围内
还有什么算法？？
问问题
326 次
2 回答
7
随机 20 位数字成为素数的机会大约为 1/20（来源）。如果您想要 x 以下的最大素数，请从x -1 开始并对每个数字运行素数测试，一直向下直到找到素数。以下是我给出的相关答案，并列出了一个足够可靠且速度极快的伪素数测试：
于 2013-05-05T17:56:37.963 回答
0
在下面使用足够多的数字筛子，n这样你就可以合理地确定它包含一个素数（比如几千个数字）。然后用小素数筛除大部分非素数。对剩余的数字使用完整的素数测试（概率或 20 位数的试除法直到根可能仍然是合理的）。
您用于筛选的小素数的数量取决于筛选与运行完整素数测试的相对成本。
于 2013-05-06T18:00:07.380 回答