Finding loop invariant I am really new concerning loop invariants and I am currently trying to figure out a loop invariant of an algorithm for prime numbers. I tried a lot of ideas, but I still have problems since there are two nested loops. I am also really grateful if someone have any tips regarding finding a loop invariant.
My idea is that all $i$ which are primes are set on true and all $i$ which are not primes are set on false.. but I don't think that this is the loop invariant.

PRIME_FILTER(n)
1  P = INIT(n) // Initialize array P[1::n] with True
2  P[1] = False
3  i = 2
4  while i * i &lt;_ n
5     if P[i] == True
6       j = i * i
7       while j &lt;_ n
8          P[j] = False // Not prime
9          j = j + i
10    i = i + 1
11 return P
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.