How to decompose a natural number into prime factors using PHP ?
At the moment there is such code:

 function factors($n = 0, $array = FALSE) { $pf = array(); for ($i = 2; $i <= $n / $i; $i++) { while ($n % $i == 0) { $pf[] = $i; $n = $n / $i; } } if ($n > 1) $pf[] = $n; return ($array === TRUE) ? $pf : implode(' * ', $pf); }

Can you do better?

  • one
    php is not suitable for this language. - zb '
  • As for the “fastest” you have to understand the theory of numbers . - VladD pm
  • Here's a review article: cs.toronto.edu/~yuvalf/Factorization.pdf - VladD
  • Interestingly, why is it even necessary, and even cross-platform? - Simply, except for cryptanalysis, nothing comes to mind, but PCP and crypto ???? - avp
  • one
    maybe a person found out how much money they give for factoring large numbers and decided "I will ask on the forum, write a program, spread it out on servers and make money." - KoVadim

1 answer 1

If the code runs under Linux, then you can call the console utility factor, which is present in many distributions. It works fast enough and uses the Pollard algorithm . An article in Wikipedia has a lot of theory and a schematic code, which, I think, can be easily ported to php.

  • Thank you, did not know about this utility, although I use Debian. But it does not solve my problem - the code should be cross-platform. - Shaftoe
  • in general, it is from the source . It is part of core utils . But it will probably be difficult to translate to php. But if you start with Wikipedia, then the link that I gave in the answer, you can find a little code. - KoVadim 2:17 pm