java - 有人可以向我解释以下素数生成方法吗？

Question

我猜下面的方法使用埃拉托色尼筛法(包含-排除算法)来生成不超过给定数的素数。我特别不明白的是，为什么它会清除 (j/2) 位置上设置的位。是否有特定的规则可遵循？ BitSet 包含在位置 x 处设置的位，这个数字要么是质数，要么是合数。所以，我无法了解正在发生的事情。

public static List<Integer> generatePrimes(int max) {
        BitSet primeSet = new BitSet(max / 2);
        primeSet.set(1, max / 2);
        int limit = (int) Math.sqrt(max);
        for (int i = 3; i <= limit; i += 2) {
            if (!primeSet.get(i / 2)) continue;
            for (int j = i * i; j < max; j += i * 2)
                primeSet.clear(j / 2);

        }

        List<Integer> listOfPrimes = new ArrayList<>();
        listOfPrimes.add(2);
        for (int i = primeSet.nextSetBit(0); i >= 0; i = primeSet.nextSetBit(i + 1)) {
            listOfPrimes.add(i * 2 + 1);
        }
        return listOfPrimes;
    }

Answer 1

看起来该算法试图通过让 primeSet 表示奇数来节省内存。因此，重复乘以和除以 2。

涉及 primeSet.clear() 的循环只是将 i 的每个倍数标记为复合。