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.

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.

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.

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).

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.