This method checks for prime numbers fast. We see how prime numbers are computed in the .NET Framework. Primes are used in many programs without the developers knowing it. The Framework provides an excellent method for testing primes.
This C# article demonstrates how to test for prime numbers. The .NET Framework algorithm is used.
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. It contains several optimizations that improve the performance of the computation. The Program class here demonstrates the results on the primes between 0 and 100, and between 10000 and 10100, proving correctness.
Program that tests IsPrime [Program.cs, C#]
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 very 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
The Main entry point is defined in the Program class in the first part of the above example. It uses 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.
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.
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', which computes the bitwise AND and pushes the result onto the evaluation stack.
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. Some code samples on the Internet do not use this optimization, which is wasteful.
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. Please notice that the method is not the exact same version found in the .NET Framework now.
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 the prime-numbers.org website to see the prime numbers over 10000 and compare our results. Additionally, you can check the first 100 prime numbers in many places.
prime-numbers.org link
Every time you use the Dictionary class in the .NET Framework, you are using the HashHelpers class as well. This class contains an integer array of prime numbers that are preferred for hashtables. These numbers were selected by the framework designers for maximum performance. Note that these integers are not the first N prime numbers, but a selection of the first N prime numbers. The GetPrime method returns the next available prime in the array.
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;
}
}
Whenever you add an element to the Dictionary constructed type 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 in the above code. 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];
// ...
// ...
}
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. Additionally, we saw how these methods are applied in the Dictionary class in the base class library, making them a part of every C# program that uses the Dictionary constructed type.
Number Examples