段上的埃拉托色尼筛法

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' 在 秒循环中??

提前致谢！！

Answer 1

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

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

公式的最后一部分，/i * i 通过使用整数 division.

的属性，找到 i 可以 div 的下一个较小的数字

示例：35 div 4 * 4 = 8 * 4 = 32，32 是（等于或）小于 35 的最大数字，它 div 可以乘以 4。

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

示例：(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) 或类似函数。我会明确表示使用了整数 division。如果不是，聪明的人可能会将其更改为常规 division，但它无法正常工作。

此外，我强烈建议包装数组。对于数字 X 的属性存储在位置 X - L 的外部并不明显。像 class RangedArray 这样的东西会为你做那个转变，让你直接输入 X 而不是 X - L，很容易承担责任。如果你不这样做，至少让它成为一个向量，在最里面的 class 之外，你不应该在 C++ 中使用原始数组。

段上的埃拉托色尼筛法

Sieve of Eratosthenes on a segment

c++

algorithm

primes

sieve

sieve-of-eratosthenes