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.

Animation linked from Wikipedia

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");
        int n = Convert.ToInt32(Console.ReadLine());

        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])


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.