了解埃拉托色尼筛法算法的修改变体

Question

我在一个编码网站（没有作者信息）上看到这个算法，它计算所有小于给定限制的素数。它看起来与 SoE 算法非常相似，但它在计算素数的方式上有所不同：

public int countPrimes(int n) {
    if (n < 3) return 0;
    boolean[] s = new boolean[n];
    int c = n / 2;
    for (int i = 3; i < Math.sqrt(n); i += 2) {
        if (s[i]) continue;
        for (int j = i * i; j < n; j += 2 * i) {
            if (!s[j]) {
                c--;
                s[j] = true;
            }
        }
    }
    return c;
}

它将初始计数设置为限制的一半然后递减它，但我似乎无法理解为什么这样做。谁能解释一下？

Answer 1

计数初始化为n/2，因为所有偶数（2除外）都不是质数。然后下面的循环可以从 3 的倍数开始检查。如果发现新的非素数 (!s[j])，则减少素数 (c) 的数量。

Answer 2

首先，布尔数组s表示SoE。

第一个循环将奇数从 3 迭代到 sqrt(n)（因为除了 2 之外的所有偶数都不是质数）。在第 6 行，如果 i 已经在 s 中，则继续下一个奇数。如果不是，则将所有小于或等于 n 的 i 的倍数添加到第二个 s循环。

另外，第二个循环是从i*i开始的，因为i的所有倍数都小于i* i 已经在之前的循环中检查过。

了解埃拉托色尼筛法算法的修改变体

Understanding a modified variant of Sieve of Eratosthenes algorithm

java

algorithm

primes