Today I was building a custom hash table implementation and needed a function that, given a number X, would find the next prime number that is equal to or greater than X.  Since X could be pretty large—on order of one trillion—I knew that done in a naive way, it could take a long time (in computer terms) to compute the next prime number.  So I started looking for a smarter way to do it.

The basic algorithm is pretty easy.  Given a number, X, the following will find the next prime number:

V = X
if (V % 2) == 0
    V += 1
while (!IsPrime(V))
{
    V += 2
}
// at this point, V is the next prime number >= X

The simplest way to determine if a number is prime is to see if it’s evenly divisible by any prime number from 2 up to and including the square root of the number in question.  That is, to determine if 101 is prime, you try dividing by 2, 3, 4, 5, 6, 7, 8, 9, and 10. If any division results in a remainder of 0, then you know that the number is not prime and you can stop testing.  Only if all the tests fail do you know that the number is prime. But the square root of one trillion is a million, and I didn’t relish the idea of doing many of millions of division operations to find the next prime number.

A much more efficient method to determine whether a number is prime is to divide it by all the prime numbers up to the square root.  It’s a simple optimization, right?  If the number is not evenly divisible by 2, then it certainly won’t be divisible by 4, 8, 296, or any other even number.  And if it’s not divisible by 5, it won’t be divisible by 10, 15, 20, or 2,465.

That insight can greatly decrease the amount of work you have to do in determining whether a number is prime.  After all, there are only 78,500 prime numbers between 0 and 1,000,000.  So the worst case goes from 500,000 division operations to 78,500.  The only catch is that you need to store all those prime numbers.  That costs some memory.  Naive encoding (four bytes per number) would take about 300K of RAM.  But you can use a table of bits and do it in about 125K.

I was halfway to building the table of primes when I decided to see just how long it takes to find the next prime using the naive method.  I quickly coded up the simplest version and got my answer.  On my machine using the naive method, it takes on average 30 milliseconds (3/100 second) to find the next prime number if the starting number is between 1 trillion and 2 trillion.  Granted, that’s a long time in computer terms.  But in context?

The reason I need to compute the next prime number is that in my hash table implementation the hash table size needs to be prime.  So if somebody asks for a table of 1 million items, I’ll give them 1,000,003.  And when I extend the table, I need to ensure that the new size is prime.  Resizing the table requires that I make a new array and then re-hash all the existing items.  That takes significant time when the table is large.  Fortunately, resizing is a relatively rare operation.

The point is that the function is called so infrequently, and the code that calls it takes so much time, that whatever cycles I spend computing the next prime won’t be noticed.  So the “slow,” simple, naive method wins.

I used to rant a lot about programmers spending their time optimizing the wrong thing, pursuing local efficiency even when it won’t affect the overall program running time. It’s embarrassing when I find myself falling into that trap.