Prime Factoring with PHP

A surprisingly large number of math based computer problems appear to require factorization, finding prime number, or prime factoring. Presented below is a reasonably fast algorithm for prime factoring a number – it is limited to the integer size on PHP (231-1). It should be a fairly trivial exercise to modify the function below to use either the bcmath or GMP arbitrary precision extensions, if this limitation must be overcome.

The basic methodology is to use a sieve to maintain an increasing list of prime numbers, and to work through those numbers until the remainder is 1. In the event that no factors are found up till the square root of the number, it is presumed that any remaining value is prime.

Execution time (Core i5, 4GB RAM, Windows/Apache (not-optimized)) is:
~35ms for n ~109
~3.5ms for n ~107
~0.6ms for n ~105

If looping through many numbers (instead of finding a single solution), maintaining the sieve array will greatly increase efficiency.

function pfactor($n){
	// max_n = 2^31-1 = 2147483647
	$d=2;
	$factors = array();
	$dmax = floor(sqrt($n));
	$sieve = array();
	$sieve = array_fill(1, $dmax,1);
	do{
		$r = false;
		while ($n%$d==0){
			$factors[$d]++;
			$n/=$d;
			$r = true;
		}
		if ($r){
			$dmax = floor(sqrt($n));
		}
		if ($n>1){
			for ($i=$d;$i<=$dmax;$i+=$d){
				$sieve[$i]=0;
			}
			do{
				$d++;
			}while ($sieve[$d]!=1 && $d<$dmax);
			if ($d>$dmax){
				$factors[$n]++;
			}
		}
	}while($n>1 && $d<=$dmax);
	return $factors;
}

Usage is quite simple - just pass a number, the return is value is an array, with keys being the prime factors, and values being the exponents:

$x=12345;
$factors = pfactor($x);
$fstr = "";
foreach ($factors as $b=>$e){
	if($fstr){$fstr .= " x ";}
	$fstr .= "$b" . ($e>1?"$e":"");
}

By cyberx86

Just a random guy who dabbles with assorted technologies yet works in a completely unrelated field.

4 comments

  1. using php5.4 this can be re-written as

    public function primeFactors($n)
        {
            // max_n = 2^31-1 = 2147483647
            $d = 2;
            $factors = [];
            $dmax = floor(sqrt($n));
            $sieve = [];
            $sieve = array_fill(1, $dmax, 1);
            do {
                $r = false;
                while ($n % $d == 0) {
                    $factors[$d] = (isset($factors[$d]) ? $factors[$d] + 1 : 1);
                    $n/=$d;
                    $r = true;
                }
                if ($r) {
                    $dmax = floor(sqrt($n));
                }
                if ($n > 1) {
                    for ($i = $d; $i <= $dmax; $i+=$d) {
                        $sieve[$i] = 0;
                    }
                    do {
                        $d++;
                    } while ($d  $dmax) {
                        $factors[$n] = (isset($factors[$n]) ? $factors[$n] + 1 : 1);
                    }
                }
            } while ($n > 1 && $d <= $dmax);
            
            return $factors;
        }
    

    note the guards when setting $factors array item and the reversal of the while ($d < $dmax && $sieve[$d] != 1 ) to guard the $sieve array. Strict error reporting prevents incrementing of unset array items.

    Thanks for the code 😉

  2. I tested both solutions above and I found problems on some numbers on first one e I couldn’t even make the second work at all. Made my own based on this algorithm (http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/) and both solutions above.

    function primeFactors($n) {
    $d = 0;
    $factors = [];
    while ($n%2 == 0) {
    $factors[2] = 2;
    $n = $n/2;
    $d++;
    }
    if($d > 0) {
    $factors[2] = $d;
    $d = 0;
    }
    for ($i = 3; $i 0) {
    $factors[$i] = $d;
    }
    }
    if ($n > 2) {
    $factors[$n] = 1;
    }
    return $factors;
    }

Leave a comment

Your email address will not be published. Required fields are marked *