algorithm - 如何找到埃拉托色尼筛算法的循环不变量？

Question

谁能帮我制作 Eratosthenes 算法的循环不变量？

这是代码的和平：

算法 埃拉托色尼筛法 输入：一个整数 n > 1。 输出：从 2 到 n 的所有素数。

let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n do
    if A[i] is true
        for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
            A[j] := false

return all i such that A[i] is true.

标签： algorithmsieve-of-eratosthenesloop-invariant

Answer 1

在第ith 次迭代之后，A[x] = false对于所有x <= n是x任何整数的倍数，j使得2 <= j <= i.