Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers
Statement (2) requires that the smallest prime number whose square exceeds $j$ is in the list. If $j=p_{n+1} &gt; (p_n)^2$, then the smallest prime number whose square exceeds $p_{n+1}$ is $p_{n+1}$ itself. As $p_{n+1}$ is not in the list while tested, (2) no longer holds.

You indeed show that all primes that are divisors of $j$ are in the list. So, an algorithm that tests all divisors in the list would be correct. However, this isn't what the algorithm in the text does, it first looks for a prime of which the square exceeds $j$, but doesn't have to be a proper divisor of $j$. 

So, the algorithm as stated in the text does require property (2), which relies on the fact that $j=p_{n+1} &gt; (p_n)^2$. In your analysis, you made the change that only the primes that divide $j$ properly need be in the list. This is a valid algorithm, but it is a different algorithm than the one in the text.

In other words, while having all primes that are proper divisors of $j$ in the list is nessecary, it isn't sufficient to run the algorithm as stated in the text.