# Finding prime numbers - Sieve of Eratosthenes

15 Mar 2016

This algorithm is used to find all prime numbers up to any given limit. This works by marking all non-composite numbers generated by multiplying with prime numbers starting from n

Following pseudo code is a variant with 2 optimization

1. The outer loop variable i will start from 2 till the square root of n
2. The inner loop variable j will start from i2
``````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 = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
A[j] := false

Output: all i such that A[i] is true.``````

Following image linked from Wikipedia shows the algorithm in action. The C# program that utilizes the optimized sieve algorithm to prints all prime number up to any given integer is shown below

``````using System;
class Program
{
public static void Main(string[] args)
{

Console.WriteLine("Enter the number upto which you want to list primes");

bool[] prime = new bool[n + 1]; // default value is false for boolean
for (int i = 2; i <= n; i++) prime[i] = true;

int limit = (int)Math.Ceiling(Math.Sqrt(n));

for (int i = 2; i <= limit; i++)
if (prime[i])
for (int j = i * i; j <= n; j += i)
prime[j] = false;

Console.WriteLine("Prime Numbers upto {0}", n);

for (int i = 0; i <= n; i++)
if (prime[i])
Console.WriteLine(i);
}

}``````

There are other variation of this algorithm that are considered to have more optimized performance.

Suggest if there is anything could be trimmed down in above code. Kindly post you views.