[issue40028] Math module method to find prime factors for non-negative int n

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Jonathan, _almost_ no factoring algorithms have any use for a table of primes.  Brute force trial division can use one, but that's about it.

A table of primes _is_ useful for implementing functions related to pi(x) = the number of primes <= x, and the bigger the table the better.  But that's not what this report is about.

Raymond, spinning up a process to factor a small integer is pretty wildly expensive and clumsy - even if you're on a box with gfactor.  This is the kind of frequently implemented thing where someone who knows what they're doing can easily whip up relatively simple Python code that's _far_ better than what most users come up with on their own.  For example, to judge from many stabs I've seen on StackOverflow, most users don't even realize that trial division can be stopped when the trial divisor exceeds the square root of what remains of the integer to be factored.

Trial division alone seems perfectly adequate for factoring 32-bit ints, even at Python speed, and even if it merely skips multiples of 2 and 3 (except, of course, for 2 and 3 themselves).

Pollard rho seems perfectly adequate for factoring 64-bit ints that _are_ composite (takes time roughly proportional to the square root of the smallest factor), but really needs to be backed by a fast "is it a prime?" test to avoid taking "seemingly forever" if fed a large prime.

To judge from the docs I could find, that's as far as gfactor goes too.  Doing that much in Python isn't a major project.  Arguing about the API would consume 10x the effort ;-)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue40028>
_______________________________________