下一个素数算法

Question

我想知道是否有简单的方法可以找到 X 旁边的素数。

例如，如果 X=2，下一个素数将是 3。如果我想知道很少的数字，但我想计算 X=300 万，我的算法就可以了。

我找到了一个计算素数的算法，但是计算它们需要很多时间，因为它计算了从0到X的所有素数...例如100万，它需要将近2分钟。

问题是...我怎样才能找到下一个素数？有没有高效的算法？我找到的最佳解决方案是检查 X+1 是否为质数并增加直到找到一个...

Answer 1

一个可能的解决方案不是将数字增加 one，如果数字是奇数，您可以将数字增加 two，否则增加 1，然后在所有未来迭代中增加 2 .

就像下面的代码片段

if (num is odd)
    check_prime_of(num+2);
else /*num is even and not equal to 2*/
    check_prime_of(num+1);

Answer 2

我可以将 "if x+1 is prime" 的速度加倍......对于所有 x > 2，那么 x+1 永远不会是素数，所以测试 x+2 :)

除此之外，没有。没有有效的算法可以找到 X 之后的下一个素数。"long time to calculate" 使 public 密钥加密（Internet 上大部分安全性的基础）成为可能。 Public key 是基于找到给定大数的两个质因数的难度；如果在 X 之后找到下一个质数很容易，那么您可以简单地从大数的平方根开始并开始计数。

Answer 3

你需要的是 test for primality each number beginning at X. You can find such tests implemented in the GMP library or you can look at the snippet for Miller-Rabin algorithm in Rosetta code.

下一个素数算法

Next prime number algorithm

algorithm

primes