在两个大数之间获取质数的高效算法

在两个大数之间获取质数的高效算法

我记得解决这样的问题：

1. 使用埃拉托色尼筛产生下面的所有素数

   sqrt(1000000000) = ~32 000

   在数组中

   primes

   。
2. 对于

   x

   之间的每个数字

   m

   ，

   n

   仅通过测试

   <= sqrt(x)

   与数组中数字的可除性来测试其是否为质数

   primes

   。因此，对于

   x = 29

   您来说，只会测试它是否可除

   2, 3 and 5

   。

检查非素数的可除性是没有意义的，因为if

x divisible by non-prime y

，则存在

p < y

诸如这样的素数

xdivisible by p

，因为我们可以写成

y

素数的乘积。例如，

12

是由整除

6

，但是

6 = 2 *3

，这意味着

12

也整除

2

或

3

。通过提前生成所有需要的素数（这种情况下很少），您可以大大减少实际素数测试所需的时间。

这将被接受，并且不需要对筛进行任何优化或修改，这是一个非常干净的实现。

您可以通过将筛子泛化以在一定间隔内生成素数来更快地完成此 *** 作

[left, right]

，

[2,right]

这与教程和教科书中通常介绍的不同。但是，这可能很难看，并且不需要。