# Understanding the pseudocode for the Sieve of Eratosthenes

The outer loop on the Wikipedia page for the Sieve of Eratosthenes ends at √n:

for i = 2, 3, 4, ..., √n :

Is this because if n has a square root it wont be prime? From what I understand this implies that any numbers above √n will also not be prime.

Why does the loop break at √n?

-

The Sieve of Eratosthenes code on Wikipedia is intended to generate a list of all primes up to $n$. Suppose $k\le n$ is not prime, so we have two factors $a,b$. We can't have $a,b$ both larger than $\sqrt{n}$, as then $k=ab$ would be larger than $n$. Thus in order to show that $k$ is prime, we only need to check that it is not divisible by a number up to $\sqrt{n}$. Equivalently (and this is the key insight in the Sieve) we only need to check that it is not divisible by a prime up to $\sqrt{n}$.