using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

          SieveOfEratosthenes(); 

    Console.WriteLine("5th prime number is " +  

                                   primes[4]); 

    Console.WriteLine("16th prime number is " + 

                                   primes[15]); 

    Console.WriteLine("10 001 prime number is " + 

                                   primes[10000]); 

    }

​

    // initializing the max value  

    static int MAX_SIZE = 10000005;

    // To store all prime numbers 

    static ArrayList primes = new ArrayList();

    // Function to generate N prime numbers using  

    // Sieve of Eratosthenes 

    static void SieveOfEratosthenes()

    {

        // Create a boolean array "IsPrime[0..MAX_SIZE]"  

        // and initialize all entries it as true.  

        // A value in IsPrime[i] will finally be false 

        // if i is Not a IsPrime, else true.  

        bool[] IsPrime = new bool[MAX_SIZE];

        for (int i = 0; i < MAX_SIZE; i++)

            IsPrime[i] = true;

        for (int p = 2; p * p < MAX_SIZE; p++)

        {

            // If IsPrime[p] is not changed, 

            // then it is a prime  

            if (IsPrime[p] == true)

            {

                // Update all multiples of p greater than or  

                // equal to the square of it  

                // numbers which are multiple of p and are  

                // less than p^2 are already been marked.  

                for (int i = p * p; i < MAX_SIZE; i += p)

                    IsPrime[i] = false;

            }

        }

​

        // Store all prime numbers  

        for (int p = 2; p < MAX_SIZE; p++)

            if (IsPrime[p] == true)

                primes.Add(p);

    }

}