C# Prime Number

Prime number. This method checks for prime numbers fast.

We see how prime numbers are computed in the .NET Framework. Primes are used in many programs—they are used in the Dictionary class. The Framework provides a method for testing primes.

Example. The algorithm here is an efficient way to determine if a specific number is a prime number. It can be found in the System.Core assembly in the .NET Framework, in the HashHelpers class.

Note: It contains several optimizations that improve the performance of the computation.

Next: This program shows the results on the primes between 0 and 100, and between 10000 and 10100, proving correctness.

Program.cs, C# program that tests IsPrime

using System;

class Program
{
    static void Main()
    {
	//
	// Write prime numbers between 0 and 100.
	//
	Console.WriteLine("--- Primes between 0 and 100 ---");
	for (int i = 0; i < 100; i++)
	{
	    bool prime = PrimeTool.IsPrime(i);
	    if (prime)
	    {
		Console.Write("Prime: ");
		Console.WriteLine(i);
	    }
	}
	//
	// Write prime numbers between 10000 and 10100
	//
	Console.WriteLine("--- Primes between 10000 and 10100 ---");
	for (int i = 10000; i < 10100; i++)
	{
	    if (PrimeTool.IsPrime(i))
	    {
		Console.Write("Prime: ");
		Console.WriteLine(i);
	    }
	}
    }
}

Class that contains IsPrime: PrimeTool.cs, C#

using System;

public static class PrimeTool
{
    public static bool IsPrime(int candidate)
    {
	// Test whether the parameter is a prime number.
	if ((candidate & 1) == 0)
	{
	    if (candidate == 2)
	    {
		return true;
	    }
	    else
	    {
		return false;
	    }
	}
	// Note:
	// ... This version was changed to test the square.
	// ... Original version tested against the square root.
	// ... Also we exclude 1 at the end.
	for (int i = 3; (i * i) <= candidate; i += 2)
	{
	    if ((candidate % i) == 0)
	    {
		return false;
	    }
	}
	return candidate != 1;
    }
}

Output

--- Primes between 0 and 100 ---
Prime: 2
Prime: 3
Prime: 5
Prime: 7
Prime: 11
Prime: 13
Prime: 17
Prime: 19
Prime: 23
Prime: 29
Prime: 31
Prime: 37
Prime: 41
Prime: 43
Prime: 47
Prime: 53
Prime: 59
Prime: 61
Prime: 67
Prime: 71
Prime: 73
Prime: 79
Prime: 83
Prime: 89
Prime: 97
--- Primes between 10000 and 10100 ---
Prime: 10007
Prime: 10009
Prime: 10037
Prime: 10039
Prime: 10061
Prime: 10067
Prime: 10069
Prime: 10079
Prime: 10091
Prime: 10093
Prime: 10099

In this example, we use two for iterative statements, which loop over the numbers 0 to 99 and the numbers 10000 to 10099. It displays all the prime numbers in those ranges by writing them to the console.

Console.Write

The IsPrime method above is defined in the PrimeTool class, and it is a public static method. This is because it does not save state and should be reused in one place rather than duplicated throughout different parts of your code.

Static Method

Bitwise AND test. The IsPrime method first uses a bitwise AND test. This tests the specific first bit, which will return true if the bits are set in that position. This generates an IL instruction "and".

IL: The "and" instruction computes the bitwise "AND" and pushes the result onto the evaluation stack.

Intermediate LanguageAnd Bitwise Operator

Incrementing by two. The for iterative statement in the IsPrime method increments the loop variable by two each time (i += 2). This is an optimization that reduces the number of iterations.

For

Update. The IsPrime method previously here had some problems in it for practical purposes. It considered 1 a prime number, and the Math.Sqrt method was slower than squaring the induction variable (i). These changes were suggested by David Simner.

Math.Sqrt

Also: Please notice that the method is no longer the same version found in the .NET Framework.

Results. Prime number methods that do not always return accurate results are worse than useless, because they would introduce bugs in your code. For this reason, we can look at a prime numbers website and compare our results.

Tip: You can check the first 100 prime numbers in many places. One option is prime-numbers.org.

Primes: prime-numbers.org

HashHelpers. Every time you use Dictionary in the .NET Framework, you are also using the HashHelpers class. This class contains an integer array of prime numbers that are preferred for hashtables. These numbers were selected for performance.

Int Array

Note: These integers are not the first N prime numbers, but a selection of the first N prime numbers.

Class that shows GetPrime method from HashHelpers: C#

public static class PrimeToolHash
{
    static int[] primes;

    static PrimeToolHash()
    {
	//
	// Initialize array of first primes before methods are called.
	//
	primes = new int[]
	{
	    3, 7, 11, 17, 23, 29, 37,
	    47, 59, 71, 89, 107, 131,
	    163, 197, 239, 293, 353,
	    431, 521, 631, 761, 919,
	    1103, 1327, 1597, 1931,
	    2333, 2801, 3371, 4049,
	    4861, 5839, 7013, 8419,
	    10103, 12143, 14591, 17519,
	    21023, 25229, 30293, 36353,
	    43627, 52361, 62851, 75431,
	    90523, 108631, 130363,
	    156437, 187751, 225307,
	    270371, 324449, 389357,
	    467237, 560689, 672827,
	    807403, 968897, 1162687,
	    1395263, 1674319, 2009191,
	    2411033, 2893249, 3471899,
	    4166287, 4999559, 5999471,
	    7199369
	};
    }

    public static int GetPrime(int min)
    {
	//
	// Get the first hashtable prime number
	// ... that is equal to or greater than the parameter.
	//
	for (int i = 0; i < primes.Length; i++)
	{
	    int num2 = primes[i];
	    if (num2 >= min)
	    {
		return num2;
	    }
	}
	for (int j = min | 1; j < 2147483647; j += 2)
	{
	    if (PrimeTool.IsPrime(j))
	    {
		return j;
	    }
	}
	return min;
    }
}

Dictionary. Whenever you add an element to Dictionary or initialize it with a specific capacity, the private instance Initialize method is called. This method uses the HashHelpers class, which contains the GetPrime method.

When the Dictionary must resize to have a capacity of more than 7199369 buckets, the IsPrime method is used in a loop. This code is not run on smaller Dictionaries but is part of all Dictionary instances.

Dictionary Initialize method: C#

private void Initialize(int capacity)
{
    int prime = HashHelpers.GetPrime(capacity);
    this.buckets = new int[prime];
    // ...
    // ...
}

Summary. Here we looked at how the .NET Framework determines whether a number is a prime number. We described the basic algorithmic design of the IsPrime method, which provides optimized logic for testing number factors.

Further: We saw how these methods are applied in the Dictionary class, making them a part of every program that uses Dictionary.

Related Links