The Sieve of Eratosthenes

~ billybudd52

Yesterday, I reviewed The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics, a book by Marcus du Sautoy.

In the book, du Sautoy explains the Sieve of Eratosthenes, an algorithm for finding all the prime numbers under a given limit.  The concept is surprisingly simple – for a set of numbers less than N, begin with the first prime number (2) and throw out all of its multiples (4, 6, 8, etc) up to N.  Then start over with the next number remaining (3) and throw out all of its multiples up to N.  Some multiples of 3, such as 6 and 12, will have been thrown out in the prior step.  Keep repeating the process until there are no numbers less than N left to be thrown out.

Example where N = 25:
– Bold numbers are the ones being eliminated in each pass.
– The number 1 is not a prime number and is ignored

Start: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
First Pass (multiples of 2): 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
Second Pass (multiples of 3):  2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25
Third Pass (multiples of 5): 2, 3, 5, 7, 11, 13, 17, 19, 23, 25
Fourth Pass (multiples of 7): 2, 3, 5, 7, 11, 13, 17, 19, 23

There are no multiples of 7 to be thrown out on the fourth pass.  Thus, there are 9 prime numbers less than or equal to 25.

Here’s a C# console app I wrote that displays every prime number less than or equal to N using the sieve algorithm.

The Sieve of Eratosthenes
  1. namespace SieveOfEratosthenes
  2. {
  3.     class Program
  4.     {
  5.         static void Main(string[] args)
  6.         {
  7.             int N = int.Parse(args[0]);
  8.             Dictionary<int, bool> nRange = new Dictionary<int, bool>();
  10.             for (int i = 2; i <= N; i++) {
  11.                 nRange.Add(i, true);
  12.             }
  14.             for (int factor = 2; factor * factor <= N; factor++) {
  15.                 if (nRange[factor] == true) {
  16.                     for (int j = factor; factor * j <= N; j++) {
  17.                         nRange[factor * j] = false;
  18.                     }
  19.                 }
  20.             }
  22.             string primes = “”;
  23.             foreach (KeyValuePair<int, bool> pVal in nRange) {
  24.                 if (pVal.Value == true)
  25.                 {
  26.                     primes = primes + Convert.ToString(pVal.Key) + ” “;
  27.                 }
  28.             }
  30.             Console.WriteLine(primes);
  31.             Console.Read();
  32.         }
  33.     }
  34. }

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.