了解Eratosthenes算法的Sieve的改进变体

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以外的所有偶数都不是质数）。在第六行，如果i已经在s中，则继续到下一个奇数。如果不是，则在第二个循环中将所有小于或等于n的i乘以s。

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