Primes, those integers that can only be divided by 1 and themselves. Here is a list of the first ten thousand prime numbers.

I find numbers extremely fascinating even though I am usually horrible at math I enjoy logical functions and algorithms and especially data structures (probably why I love object orientated languages so much.)  Recently I was playing with some concepts of on demand generated websites that could generate thousands of unique pages utilizing very few lines of code. There are lots of ways to do this, but at the same time I felt one of the goals must be to also generate on those pages some kinds of useful and/or meaningful information.

Within a couple of days I had a little less than thousand lines of code and about 5 web page templates put together to generate every prime number between 1 and 9,223,372,036,854,775,807. That is nine quintillion two hundred twenty-three quadrillion three hundred seventy-two trillion thirty-six billion eight hundred fifty-four million seven hundred seventy-five thousand eight hundred seven.

It’s important because it’s the limiting factor of a 64 bit integer. You’ve probably heard that computer code is really 0’s and 1’s, that’s right. In binary we count using only the digits 0 and 1 instead of 1 through 10 but you add and carry exactly the same.

0001 = 1

0010 = 2

0011 = 3

but when you have 63 of these all set to 1

111111111111111111111111111111111111111111111111111111111111111

it comes out to our magic number of 9,223,372,036,854,775,807.

Why not 64 digits? Because the last bit in PHP is reserved for indicating positive or negative. Some languages such a C allow you to extend the number by sacrificing negative numbers, this is referred to as an “unsigned integer”. But PHP does not support unsigned.

So I put this website together to try and extrapolate interesting information about numbers at IntegerNumber.com, things such as is it a prime number, what divisors and factorization values does it contain, simple hash codes and other base representations besides the standard base 10 and binary.

Just imagine however if Google or another search engine was to try and crawl and index every one of those pages. If Google could crawl 1 page a second, it would take 292,277,506,246 years to crawl every page. That is 20 times the current age of the universe. Also at roughly 1k bits of information per page the storage capacity required would be…my calculator broke…let us say lot 🙂

So to be nice to my hosting provider I decided to limit it to the integer 2,147,483,647 which is max for a 32 bit integer with a length of 31 binary 1’s. Am I not merciful.

I had run across a few code snippets of other code slingers discussing algorithms that could run fast enough for real time processing to calculate prime numbers be determining the divisors.  Being the egotistical coder I am I didn’t even bother looking at their code before quickly pulling up my notepad and jotting down a quick for loop to do just that.

The function seemed to work well enough for small integers but at larger numbers in excessive of several million the time to process the loop was excessive.  So then the fun begins, well I find it fun, a puzzle to solve, kind of like solving a Sudoku.  Figure out how to reduce the number of operations to solve the problem.

It is obvious that no divisor is greater than half the number, so (n/2) cuts the operation literally in half. But still larger integers were a taking way too long. So then reading up on some math you can calculate factorizations based on square roots that divide to equal zero. However now we are left with a factorization that looks like this: 2 * 3² * 7 * 11 * 31 * 151 * 331 for the Integer 2147483647 (the highest 32 bit integer in PHP.) Finding the factorization based on the square root of the number is quick and then you simply have to calculate every permutation. A simple sort function gets the work done in O(n^2).

Once you have the number of divisors you only have to count the number to determine if it is prime, which is two, 1 + itself.

function primefactor($num)
	{
	$sqrt = sqrt($num);
	for ($i = 2; $i <= $sqrt; $i++)
		{
		if ($num % $i == 0)
			{
			return array_merge(primefactor($num/$i), array($i));
			}
		}
	return array($num);
	}

function divisors($primes,$num)
	{
	$num_primes = count($primes);
	$divisors = Array();

	$limit = pow(2, $num_primes) - 1;

	for($number = 0; $number <= $limit; $number++)
		{
	  $divisor = 1;
		for($i = 0; $i < $num_primes; $i++)
			{
			$divisor *= ($number >> $i) & 1 ? $primes[$i] : 1;
			}
		$divisors[] = $divisor;
		}

	sort($divisors);
	return array_unique($divisors);
	}