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":"");
}
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
$factorsarray item and the reversal of the while ($d < $dmax && $sieve[$d] != 1) to guard the$sievearray. Strict error reporting prevents incrementing of unset array items.Thanks for the code 😉
Thanks for the suggestions and code – looks good.
beautiful solution and quite fast
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;
}