Finding loop invariant
Let's see what the algorithm does in its first few iterations:

Mark all elements other than 1 as &quot;potentially prime&quot;.
Mark all multiples of 2, starting at 4, as &quot;not prime&quot;.
Mark all multiples of 3, starting at 9, as &quot;not prime&quot;.
Skip 4, since it is known to be not prime.
Mark all multiples of 5, starting at 25, as &quot;not prime&quot;.
Skip 6, since it is known to be not prime.
Mark all multiples of 7, starting at 49, as &quot;not prime&quot;.

So it continues, until the next element is already larger than $\sqrt{n}$.
Here is how we can describe the contents of the array:

All elements other than 1 are &quot;potentially prime&quot;.
All elements not divisible by 2 are &quot;potentially prime&quot;, except for 2.
All elements not divisible by 2,3 are &quot;potentially prime&quot;, except for 2,3.
All elements not divisible by 2,3,4 (equivalently, by 2,3) are &quot;potentially prime&quot;, except for 2,3.

And so on.
Hopefully this gives you some ideas on the loop invariant.