Prime Numbers Part 1 - Introduction

Prime numbers appear everywhere in science and nature. They're very handy when it comes to solving puzzles as well, so it having a generator would be useful.

Unfortunately .NET doesn't seem to have a usable prime number generator class, and neither does the C++ Standard Library. It seems that if you want one, you need to write one.

Ruby has some quite nice prime generation facilities built in, and as of version 1.9 they're quite fast (for a scripted language!). It might be worth looking at how the Ruby designers implemented their classes later, and seeing if we can improve on them.

Let's start with the (very) basics. If we want to generate prime numbers, we need a way to check whether a number is prime or not.

Testing for Primality

We know the following:

• The lowest prime number is 2.
• 2 is the only even prime number.
• Prime numbers have no factors other than themselves and 1. Every whole number has 1 as a factor, so there's not much point checking for that.

We'll call our function "IsPrime", and make it a static class member - there's no state information in the function, it just checks a value and returns. Later we can see whether there's anywhere better to put the function.

namespace SoftwarePragmatism
{
  public class Primes
  {
    // Other stuff chopped out here
 
    public static bool IsPrime(long number)
    {
      if (number == 2)
      {
        return true;
      }
 
      if ((number <= 1) || (number % 2 == 0))
      {
        return false;
      }
 
      long root = (long)Math.Sqrt(number);
 
      for (long divisor = 3; divisor <= root; divisor += 2)
      {
        if (number % divisor == 0)
        {
          return false;
        }
      }
 
      return true;
    }
  }
} 

Looking at the code you can see it does the following in order

1. Check to see whether 'number' is 2. If it is, return true because 2 is prime.
2. Check to see whether 'number' is less than 2 or divisible by 2. In either case, it's not prime so return false.
3. Loop through all of the odd numbers from 3 to the square root of 'number'. If any of these numbers are a factor of 'number', it isn't prime, so return false.

If we made it through all this, and still didn't find any factors, then 'number' was prime, so return true.

If this looks inefficient to you, that's because it is. If you wanted to check whether, say, 1,000,001 was prime, the final loop would run from 3 to 999. Imagine trying to filter out prime numbers from 2 to 1,000,001, and suddenly that loop runs through hundreds of millions of iterations!

There's got to be a better way, and there is, but this will do for the moment. One thing to stick to when you're coding is "Make it work properly, then make it work quickly".