Prime Number Testing

A prime number (or a prime) is defined as a positive integer greater than 1 that has no positive divisors other than 1 and itself. If I wanted a programmatic test that a number is prime, my first instinct in C# would look something like this:

        
static bool IsPrime(int number)
{
	for(int i = 2; i < number; ++i)
	{
		if(number % i == 0)
		{
			return false;
		}
	}
	return true;
}

There are a couple problems with this approach. First off the trivial test for IsPrime(2) yields false. Also the C# int data type has positive and negative numbers, so there will need to be a check that the number is positive, but since we know 2 is the smallest prime, we can just check if the number is less than 2. (For more sophisticated use cases, exception handling might be needed for negative numbers.)

static bool IsPrime(int number)
{
	if (number < 2) return false; 
	if (number == 2) return true;
	for(int i = 2; i < number; ++i)
	{
		if(number % i == 0)
		{
			return false;
		}
	}
	return true;
}

So, this function is pretty good, right? By the mathematical definition of prime numbers there is nothing wrong with this function, but a simple test shows us that it is very slow to handle large numbers.

static void Main(string[] args)
{
	var stopwatch = new Stopwatch();
	stopwatch.Start();

	for(int i = int.MaxValue; i>0; i--)
	{
		
		if (IsPrime(i) == true)
		{
			stopwatch.Stop();
			Console.WriteLine(i.ToString() + " found in a time of " + stopwatch.Elapsed);
			Console.WriteLine("Total numbers tested: " + (int.MaxValue - (i - 1)).ToString());
		}            
	}
}

2147483647 found in a time of 00:00:08.5264074
Total numbers tested: 1
Done

Ouch. Now imagine if we chose to use long instead of int. (Protip: With modern processing, it would take about 6000 years to run this algorithm against the largest Int64 prime. Don’t try this at home, kids.) This is not a function I would add to a deliverable! But fear not! We can math this up a bit and runtime will thank us.

We’ll start by looking at the number 20.
Other than the trivial divisors, 20 can be evenly divided by four numbers listed in ascending order: 2, 4, 5, 10.
Now let’s look at 45: 3, 5, 9, 15.
Finally, observe 77: 7, 11.

Note that the product of the outside divisors is the original number. This implies that a number (N) divided by its least possible divisor (LPD) equals it’s greatest divisor (GPD). In other words the greatest possible divisor of a number cannot exceed that number divided by its least possible divisor.

What this tells us is that if a number is not prime that we have information about it’s greatest divisor – namely that: GPD=N/LPD. As we iterate through numbers to identify the LPD-GPD pair, the pool of numbers that could contain the GPD gets smaller. Right away it’s clear that since an odd number is not divisible by 2 that its GPD must be less than N/2. Look at 45. (Note that for the illustration decimal values are used. Integer values are rounded down and just as correct.)

45 mod 2 = 1 (ie 45 / 2 = 22 with 1 remaining)
The GPD must be less than 22.5.
Try 3.
45 mod 3 = 0
45/3 = 15. GD = 15.

Look at 77.
77 mod 2 = 1
The GPD must be less than 38.5.
77 mod 3 = 2
The GPD must be less than 25.6667.
77 mod 4 = 1
The GPD must be less than 19.25.
77 mod 5 = 2
The GPD must be less than 15.4
77 mod 6 = 5
The GPD must be less than 12.8333
77 mod 7 = 0
The GPD is 11.

If a number is prime we can apply the same algorithm to reduce the number of tries. For every try at identifying an LPD the maximum GPD is N / LPD. We will start off by defining GPD as the number, ie the trivial N/1. As LPDs increase, GPDs will decrease.

static bool IsPrime(int number)
{
	int GPD = number;

	if (number < 2) return false; 
	if (number == 2) return true;
	for(int LPD = 2; LPD < GPD; ++LPD)
	{
		if(number % LPD == 0)
		{
			return false;
		}
		GPD = number / LPD;
	}
	return true;
}

2147483647 found in a time of 00:00:00.0004447
Total numbers tested: 1
Done

This is much better. We reduced the GPD from 2,147,483,647 to 46,341 and the efficiency of the algorithm for the maximum integer has improved from over 8s to less than 1ms.