11. Primality testing

One simple way to determine whether a number N is prime is to loop through all of the integers between 2 and N – 1 and use the modulus operator % to see if any of them divide the number evenly. There are a couple of ways that you can improve this approach.

First, note that once you check a potential divisor, you don't need to check any multiples of that divisor. For example, if 2 doesn't divide evenly into N, then 4, 6, 8, and other multiples of 2 also cannot divide evenly into N. To make the basic approach faster, you can test the divisor 2 separately and then make the loop consider only odd numbers.

You can also improve this method by changing the loop's upper limit. The original method considers values between 2 and N – 1, but you can change the upper limit to . To see why that works, suppose N has a factor A where A > , so the loop won't find A. In that case, N = A × B for some value, B. If A > , then B must be less than , so the loop won't find A, but it will find B.

Making the loop consider only odd numbers and making the loop end at  gives the following method for determining whether a number is prime:

// Return true if the number is prime.
private bool IsPrime(long number)
{
    // Handle 2 separately.
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    // See if the number is divisible by odd values up to Sqrt(number).
    long sqrt = (long)Math.Sqrt(number);
    for (long i = 3; i <= sqrt; i += 2)
        if (number % i == 0) return false;

    // If we get here, the number is prime.
    return true;
}

Note that this method only uses numbers that are smaller than N, so it cannot cause an integer overflow.

Download the PrimalityTesting example solution to see additional details.