Sieve of Eratosthenes


Sieve of Eratosthenes is an ancient algorithm for finding prime numbers developed by the great mathematician Eratosthenes. Although the algorithm is centuries years old, it is still widely in use and considered one of the most common algorithms for generating prime numbers. There are couple of algorithms that outperform this one, the Sieve of Atkins and the Sieve of Subarama. I will discuss these on future posts but for the moment lets dig into Eratosthenes’s algorithm:

The algorithm takes as input an integer N, and generates all primes from 2 up to N. It works as follows:

  • generate all numbers from 2 up to N in ascending order
  • since 2 is the first prime, walk through the list of numbers and eliminate every second number from it
  • grab the next integer that survived the elimination(which is 3), and eliminate every third number from the list
  • then grab the next integer that survived that elimination(which is 5) and repeat the same process until the square of the next grabbed number is greater than N

Below is a graphical representation of the algorithm from Wikipedia:
.

It is easy to implement and test this algortihm in few lines of code. Create a console application and replace the main method with the following one and we’re done🙂 (Special greetings to Mohammad Selek who contributed the source code).

     Sub Main()
        Dim s As String
        Console.Write("Find primes up to: ")
        s = Console.ReadLine
        Dim upperLimit As Integer = s.Trim
        Dim prime(upperLimit) As Integer
        Dim c1, c2, c3 As Integer
        For c1 = 2 To upperLimit
            prime(c1) = 0
        Next
        prime(0) = 1
        prime(1) = 1
        For c2 = 2 To Math.Sqrt(upperLimit) + 1
            If prime(c2) = 0 Then
                c1 = c2
                c3 = 2 * c1
                While c3 < upperLimit + 1
                    prime(c3) = 1
                    c3 = c3 + c1
                End While
            End If
        Next
        For c1 = 0 To upperLimit
            If prime(c1) = 0 Then
                Console.Write(c1 & "     ")
            End If
        Next
        Console.ReadKey()
    End Sub

Here is the output when N=1000

3 Responses to Sieve of Eratosthenes

  1. Excellent post! We can use a simple modification to the Sieve of Eratosthenes – we can start eliminating multiples of found primes, starting from the square of that prime.

    For example, if 7 is found to be prime, we eliminate multiples of 7 starting from 49. This reduces the running time to a great extent in case of a large upper limit.

    Check out my post on this prime sieve: http://thecodeaddict.wordpress.com/2011/11/01/sieve-of-eratosthenes/

  2. Ali Tarhini says:

    great idea, let me know how much speedup we get if you try it

  3. the code to start from the square, combined with the fact that we only need to check for odd multiples of a prime number, ran in approx 64% of the time taken by a simpler implementation.

    For finding all prime numbers below 2 million, the modified algorithm ran in 15 milliseconds in Java

Leave a Reply

Please log in using one of these methods to post your comment:

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

%d bloggers like this: