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

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;
}

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

标签： javaalgorithmprimes

Answer 1

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