using System;

using System.Collections.Generic;

using System.Collections.Specialized;

​

public class BitVector

{

    private readonly BitVector32[] vector;

    public BitVector(int size,bool fillZero = true)

    {

        int vectorArraySize = size >> 5; // divide by 32, gives number of 32 multiples

        if((size & 31) > 0)

        {

            vectorArraySize += 1; // size may not be an exact multiple of 32, so add 1 more in the integer array to accommodate that

        }

        vector = new BitVector32[vectorArraySize];

        if(fillZero == false)

        {

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

            {

                vector[i] = new BitVector32(-1);

            }

        }

    }

    public void ClearBit(int bitNum)

    {

        int idx = bitNum >> 5;

        int offset = bitNum & 31;

        int mask = (1 << offset);

        vector[idx][mask] = false;

    }

    public bool testBit(int bitNum)

    {

        int idx = bitNum >> 5;

        int offset = bitNum & 31;

        int mask = (1 << offset);

        return vector[idx][mask];

    }

    public void setBit(int bitNum)

    {

        int idx = bitNum >> 5;

        int offset = bitNum & 31;

        int mask = (1 << offset);

        vector[idx][mask] = true;

    }

    public void Print()

    {

        foreach(BitVector32 val in vector)

        {

            Console.WriteLine("Values in BitVector : {0}",val.ToString());

        }

    }

}

public class Program

{

    public static void Main()

    {

        //Console.WriteLine("Is 1073 Prime ? : {0}", IsPrime(1171));

        Console.WriteLine("List of Prime Numbers till 1171 : {0}", string.Join(",",ListOfPrimesSimple(1171)));

        Console.WriteLine("List of Prime Numbers till 1171 : {0}", string.Join(",",ListOfPrimes(1171)));

    }

    public static bool IsPrime(int n)

    {

        if(n <= 1) return false;

        if(n == 2) return true;

        if(n%2 == 0) return false;

        /*

        * Checking till sqrt is enough, as one of the multiple has to be <= sqrt(n)

        * i = i+2 , we need not validate if it's divisble by any even number.

        */

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

        for(int i = 3; i <= sqrt; i=i+2)

        {

            if(n%i == 0)

            {

                Console.WriteLine("Divisible by {0}",i);

                return false;

            }

        }

        return true;

    }

    public static List<int> ListOfPrimes(int n)

    {

        List<int> result = new List<int>();

        if(n > 1)

        {

            BitVector v = new BitVector(n+1,false);

            //v.Print();

            for(int i = 2; i <= n; i++)

            {

                //Console.WriteLine("Testing Bit : {0}",i);

                if(v.testBit(i) == true)

                {

                    result.Add(i);

                    int j = i*2;

                    while(j <= n)

                    {

                        //Console.WriteLine("Clearing Bit : {0}", j);

                        v.ClearBit(j);

                        j += i;

                    }

                }

            }

        }

        return result;

    }

    public static List<int> ListOfPrimesSimple(int n)

    {

        List<int> result = new List<int>();

        if(n > 1)

        {

            bool[] primes = new bool[n+1];

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

            {

                primes[i] = true;

            }

            for(int i = 2;i <= n; i++)

            {

                if(primes[i] == true)

                {

                    result.Add(i);

                    int j = i*2;

                    while(j <= n)

                    {

                        primes[j] = false;

                        j += i;

                    }

                }

            }

        }

        return result;

    }

}