Algorithms

Sieve of Eratosthenes

The most efficient way to find all of the small primes (say all those less than 10,000,000) is by using a sieve such as the Sieve of Eratosthenes.

 


Algorithm:

Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, …, not exceeding √n:
if A[i] is true:
for j = i^2, i^2 + i, i^2 + 2i, …, not exceeding n :
            A[j] := false

Explanation:
Let’s find all primes from less than 25, we have

The first number 2 is prime, so keep it (color it green) and cross out its multiples (color them red), so the red numbers are not prime.

The first number left (still black) is 3, so it is the first odd prime. Keep it and cross out all of its multiples. We know that all multiples less than 9 (i.e. 6) will already have been crossed out, so we can start crossing out at [math]3^2 = 9[/math].

Now the first number left (still black) is 5, the second odd prime. So keep it also and cross out all of its multiples (all multiples less than [math]5^2 = 25[/math] have already been crossed out, and in fact 25 is the only multiple not yet crossed out).

The next number left, 7, is larger than the square root of 25, so there are no multiples of 7 to cross off that haven’t already been crossed off (14 by 2, and 21 by 3), and therefore the sieve is complete. Therefore all of the numbers left are primes: {2, 3, 5, 7, 11, 13, 17, 19, 23}.

And we are done!

BTW the best way to understand this is by this gif. File:Sieve of Eratosthenes animation.gif

 

I posted it here.

Advertisements

One thought on “Sieve of Eratosthenes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s