Prime Number Calculation in C#

10 Nov 2013

C#, Maths

A simple method for prime calculation involves:

• Calculate the square root of the number
• Setup a positively incrementing loop from 2 to the square root
• Attempt to divide the number by the loop value
• If the result of this calculation is greater than zero, then we will consider the integer to be prime
• If we encounter one zero result in this loop, we will consider the integer to NOT be prime

Example 1: Is 3 a prime?

• The square root of 3 is 1.73, boxed to an Int64 value however becomes 1
• It is not possible to set up a positively incrementing loop from 2 to 1
• Therefore, 3 is a prime number

Example 2: Is 27 a prime?

• The square root of 27 is 5.19, boxed to an Int64 value however becomes 5
• Setup a positively incrementing loop from 2 to 5
  • 27 mod 2 = 1 - could be a prime, as the result is greater than 0
    • Continue to the next iteration
  • 27 mod 3 = 0 - now we know that 27 is divisible by a number other than 1 and itself
    • Exit the loop
• Therefore, 27 is not a prime number

Example 3: Is 392 a prime?

• The square root of 392 is 19.79, boxed to an Int64 value however becomes 19
• Setup a positively incrementing loop from 2 to 19
  • 392 mod 2 = 0 - now we know that 392 is divisible by a number other than 1 and itself
    • Exit the loop
• Therefore, 392 is not a prime number

The code is quite simple, and is presented here written as an extension.

#region Using References 

using System; 

using Maths = System.Math; 

#endregion 

public static class Extensions 
{ 
    #region Methods 

    public static bool IsPrime(this long Value) 
    { 
        bool bIsPrime = true; 

        // Assume that the integer supplied is actually a prime, then test for
        // statements that make this condition false
        long lSquareRoot = (long)(Maths.Sqrt(Value)); 

        for (long l = 2; l <= lSquareRoot; l++) 
        { 
            //  If the result of this calculation is greater than zero, then we will consider the integer to be prime
            //  If we encounter one zero result in this loop, we will consider the integer to NOT be prime

            bIsPrime = ((long)(Value % l) > 0); 

            if (bIsPrime == false) 
            { 
                // Break out of the loop
                break; 
            } 
        } 

        return bIsPrime; 
    } 

    #endregion 
}