# Prime Factoring with PHP

This post was published 9 years, 8 months ago. Due to the rapidly evolving world of technology, some concepts may no longer be applicable.

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?"<sup>\$e</sup>":""); }```

## 4 thoughts on “Prime Factoring with PHP”

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 😉

• cyberx86 on said:

Thanks for the suggestions and code – looks good.

2. Luis Naia on said:

beautiful solution and quite fast

3. 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;
\$n = \$n/2;
\$d++;
}
if(\$d > 0) {
\$factors = \$d;
\$d = 0;
}
for (\$i = 3; \$i 0) {
\$factors[\$i] = \$d;
}
}
if (\$n > 2) {
\$factors[\$n] = 1;
}
return \$factors;
}