Thursday, March 15, 2007

C# - Counting the number of primes

Recently I had to figure the number of primes below a given number n. One way to start at 2, go all the way till n, and check if any of the numbers are a multiple of any of the numbers upto n. This is not the most efficent solution though. The sieve of Eratosthenes is an elegant solution to this problem. http://mathworld.wolfram.com/SieveofEratosthenes.html Basically, it says that you need to check if every number from 2 to n, is a multiple of every number from 2 to the floor of the square of n. One can skip all those numbers that have already been set as not a prime, and the test of multiples can be started at 2*currentNumber being checked - as that will be the first multiple of the number currentNumber. (The code is self explanatory and Wolfarm has a sieve example). Though this code makes fewer checks and hence is faster (it is inefficent for larger values of n, as it needs to allocate an array of size n) In addition there is a function to output n primes - which uses the traditional check for primes. Which can also used to count the number of primes below n. Here is the solution in C#:
using System;
using System.Collections.Generic;

public class SieveofEratosthenes
{
    //based on Sieve of Eratosthenes http://mathworld.wolfram.com/SieveofEratosthenes.html
    static int CountPrimes(int countTill)
    {
        bool []primes = new bool[countTill+1];//we are counting upto this number
        int checkTill = (int)Math.Floor(Math.Sqrt((double)countTill));//according to Eratosthenes -
        //we need to check only till the floor of the square
        for (int index = 1; index <= countTill; index++)
            primes[index] = true;
       
        for (int i = 2; i <= checkTill; i++)
        {
            if (!primes[i])
                continue;//can continue - as its not a prime and hence would have crossed out numbers
           
            for (int j = i*2; j <= countTill; j++)
            {
                if ((j % i) == 0)
                {
                    //is a multiple of i - there fore not a prime!
                    primes[j] = false;
                }
               
            }
        }
       
        int count = 0;
        for (int i = 2; i <= countTill; i++)
        {
            if (primes[i])
                count++;
        }
        return count;
    }
   
    public static bool IsPrime(int currentNumberToCheck)
    {
        int currentDivisor = 2;
        int checkTill = currentNumberToCheck/2;
        while(currentDivisor <= checkTill)
        {
            if (currentNumberToCheck % currentDivisor == 0)
            {
                return false;
            }
            currentDivisor++;   
        }
        return true;
    }
    public static void PrintNPrimes(int n)
    {
        int count = 0;
        int currentNumberToCheck = 2;
        while (count < n)
        {
            if (IsPrime(currentNumberToCheck))
            {
                WL(currentNumberToCheck);
                count++;
            }
            currentNumberToCheck++;
        }
    }
   
    public static void Main()
    {
        WL(CountPrimes(100));
        PrintNPrimes(25);
        RL();
    }
   
    #region Helper methods

    private static void WL(object text, params object[] args)
    {
        Console.WriteLine(text.ToString(), args);   
    }

    private static void RL()
    {
        Console.ReadLine();   
    }

    #endregion
}

No comments: