Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

up vote 1 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|improve this answer
add comment

Your Answer

 
discard

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.