## 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