我记得解决这样的问题：
- 使用埃拉托色尼筛产生下面的所有素数
sqrt(1000000000) = ~32 000
在数组中primes
。 - 对于
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]这与教程和教科书中通常介绍的不同。但是，这可能很难看，并且不需要。
