.NET Array Collections File String Async Cast DataTable DateTime Dictionary Enum Exception For Foreach IEnumerable If IndexOf Lambda LINQ List Parse Path Process Property Regex Replace Sort Split StringBuilder Substring Switch Tuple

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.

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 IsPrimeusing 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 boolIsPrime(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.

**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".

**IL:**The "and" instruction 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.

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.

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.

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 intGetPrime(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 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];// ... // ...}

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.