Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.