Home
C#
Prime Number
This page was last reviewed on Mar 17, 2023.
Dot Net Perls
Prime numbers. A prime number has no divisors (other than itself and 1). This method checks for prime numbers fast. Prime numbers are computed in the .NET Framework.
Primes are used in many programs—they are used in the Dictionary class. They help with hashing. The .NET Framework provides a method for testing primes.
An example. The algorithm here determines 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 IsPrime is defined in the PrimeTool class, and it is a public static method. It does not save state.
static
Note 2 The IsPrime method first uses a bitwise AND test. This tests the specific first bit.
And This is an optimization that reduces the number of iterations. Even numbers are skipped over.
Finally We loop over the numbers 0 to 99 and the numbers 10000 to 10099. We display all the prime numbers.
for
Console.WriteLine
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); } } } }
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; } }
--- 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
HashHelpers. This is used in Dictionary. 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.
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.
Dictionary
And This method uses the HashHelpers class, which contains the GetPrime method.
Tip When the Dictionary must resize to have a capacity of more than 7199369 buckets, the IsPrime method is used in a loop.
Tip 2 This code is not run on smaller Dictionaries but is part of all Dictionary instances.
private void Initialize(int capacity) { int prime = HashHelpers.GetPrime(capacity); this.buckets = new int[prime]; // ... // ... }
Update. The IsPrime method previously here had some problems. It considered 1 a prime number, and the Math.Sqrt method was slower than squaring the induction variable (i).
Math.Sqrt
Important Please notice that the method is no longer the same version found in the .NET Framework.
A summary. This logic determines whether a number is a prime number. We described the algorithmic design of the IsPrime method, which provides optimized logic for testing number factors.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Mar 17, 2023 (edit).
Home
Changes
© 2007-2024 Sam Allen.