This is a simple and ancient algorithm for finding all prime numbers up to a given number, say n. Although it is a very, very old algorithm, it works fairly efficiently for numbers under 10 million. As the name suggests, this algorithm was created by a Greek mathematician by the name of Eratosthenes…

The following is the algorithm he suggested:

Simply make a list of consecutive numbers from 2 up to the number n. Now, take each number from the front of the list (first 2, then 3 and so on) and remove the multiples of each of these numbers from the rest of the list starting from the square of the number.  At the end of this procedure, all remaining numbers are prime…

Therefore, in essence, we keep removing elements over and over using one number at a time to choose the numbers that must be removed.

Here’s a working version of the algorithm. Say we want all prime numbers from 1 to 20.

Step 1: Make a list of all numbers from 2 to 20

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Step 2: Take the first number i.e. 2 and remove all its multiples from the list starting from 4.

2  3  5  7  9  11  13  15  17  19

Step 2: Take the next number (2nd number) i.e. 3 and remove all its multiples from the list starting from 9

2  3  5  7  11  13  17  19

Step 3: Take the next number (3rd number) i.e. 5 and remove all its multiples from the list starting from 25. But, since 25 is greater than our n = 20, the process stops at this step.

Therefore, our final list of prime numbers is:

2  3  5  7  11  13  17  19

And yay! that’s the right answer… and computationally easy and efficient!

Advertisements