Quickest Way to Find Prime (PHP)

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);
	}