c++ - 段上的埃拉托色尼筛法

Question

段上的埃拉托色尼筛法:有时您需要找到范围内的所有素数[L...R] 而不是 [1...N]，其中 R 是一个大数。

条件:您可以创建一个整数数组，大小为(R−L+1).

实现:

bool isPrime[r - l + 1]; //filled by true
for (long long i = 2; i * i <= r; ++i) {
    for (long long j = max(i * i, (l + (i - 1)) / i  * i); j <= r; j += i) {
        isPrime[j - l] = false;
    }
}
for (long long i = max(l, 2); i <= r; ++i) {
    if (isPrime[i - l]) {
        //then i is prime
    }
}

在中设置'j'的下限背后的逻辑是什么>第二个 for 循环??

提前致谢!

Answer 1

想想我们想要找到什么。忽略 i*i 部分。我们只有(L + (i - 1))/i * i) 来考虑。 (我写了大写的L因为l和1看起来很像)

应该是什么？显然它应该是 L..R 中能被 i 整除的最小数。那就是我们要开始筛选的时候了。

公式的最后一部分，/i * i 利用整数除法的性质，找到下一个可被 i 整除的小数。

示例:35 div 4 * 4 = 8 * 4 = 32，32 是(等于或)小于 35 的可被 4 整除的最大数字。

显然，L 是我们要开始的地方，而 + (i-1) 确保我们找不到等于或小于 L 的最大数，但等于或大于 L 的最小数可以被整除一、

示例:(459 + (4-1)) div 4 * 4 = 462 div 4 * 4 = 115 * 4 = 460。

460 >= 459, 460 | 4、具有该性质的最小数

(max( i*i, ...) 只是为了让 i 在 L..R 内时不会被筛掉，我想，虽然我想知道为什么它不是 2 * i)

出于可读性的原因，我将其设为内联函数 next_divisible(number, divisor) 或类似函数。我会明确表示使用了整数除法。如果不是，聪明的人可能会将其更改为常规除法，但它不会起作用。

此外，我强烈建议包装数组。从外部看，数字 X 的属性存储在 X - L 位置并不明显。类似 RangedArray 的类可以为您进行移位，允许您直接输入 X 而不是X-L，很容易承担责任。如果你不这样做，至少让它成为一个 vector ，在最里面的类之外，你不应该在 C++ 中使用原始数组。