How to factor using Python?

[Mensanator]

On Mar 10, 12:48 am, Gabriel Genellina <gagsl-... at yahoo.com.ar> wrote:
> On 10 mar, 02:08, Nathan Pinno <MadComputer... at gmail.com> wrote:
>
> > How do I factor a number?

If factoring is actually what you want, the sympy module can do it.

>>> n = 85085**3
>>> print n
615969217989125
>>> import sympy
>>> f = sympy.factorint(n)
>>> f
[(5, 3), (7, 3), (11, 3), (13, 3), (17, 3)]
>>> ff = [[i[0]]*i[1] for i in f]
>>> ff
[[5, 5, 5], [7, 7, 7], [11, 11, 11], [13, 13, 13], [17, 17, 17]]
>>> fff = sympy.flatten(ff)
>>> fff
[5, 5, 5, 7, 7, 7, 11, 11, 11, 13, 13, 13, 17, 17, 17]

Provided that your needs are modest. It claims to be
able to handle 10 digit factors, but it certainly can't
handle numbers of this magnitude:

50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749

As it takes a couple hours of run-time only to crash
with an out of memory error.

If you need to handle something like that, you may want to
get factor.exe which is part of the MIRACL library. The library
is in C and doesn't have a Python interface, but you can run
the .exe from Python and capture the output.

Keep in mind two things: factor.exe doesn't have consistent
output making it more difficult to interpret the captured
output. I re-compiled my copy of factor.exe to provide
consistent output.

The other thing is that factor.exe sometimes gets confused
claiming a number is composite that factor.exe is fully
capable of factoring. Luckily this can be easily fixed in
the Python program that calls it.

In the following example, if factor!.exe (my re-compiled
version) returns any composites, I simply feed them back
into the program until all are factored or determinened to
be truly intractable.

Note the times. If you have serious factoring needs, the
MIRACL solution is better than sympy.

##  ========================================
##  Phase 1
##  ['COMPOSITE_FACTOR',
'50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749']
##
##  ['PRIME_FACTOR', '37']
##  ['PRIME_FACTOR', '43']
##  ['PRIME_FACTOR', '167']
##  ['COMPOSITE_FACTOR', '507787751']
##  ['PRIME_FACTOR', '69847']
##  ['PRIME_FACTOR', '30697']
##  ['PRIME_FACTOR', '89017']
##  ['PRIME_FACTOR', '3478697']
##  ['PRIME_FACTOR', '434593']
##  ['PRIME_FACTOR', '49998841']
##  ['PRIME_FACTOR', '161610704597143']
##  ['PRIME_FACTOR', '14064370273']
##  ['COMPOSITE_FACTOR', '963039394703598565337297']
##  ['PRIME_FACTOR', '11927295803']
##
##  0.860000133514 seconds
##  ========================================
##  Phase 2
##  ['COMPOSITE_FACTOR', '507787751']
##
##  ['PRIME_FACTOR', '29819']
##  ['PRIME_FACTOR', '17029']
##
##  0.0780000686646 seconds
##  ========================================
##  Phase 3
##  ['COMPOSITE_FACTOR', '963039394703598565337297']
##
##  ['PRIME_FACTOR', '518069464441']
##  ['PRIME_FACTOR', '1858900129817']
##
##  0.0469999313354 seconds
##  ========================================
##
##  Factoring complete
##
##  PRIME_FACTOR 37
##  PRIME_FACTOR 43
##  PRIME_FACTOR 167
##  PRIME_FACTOR 17029
##  PRIME_FACTOR 29819
##  PRIME_FACTOR 30697
##  PRIME_FACTOR 69847
##  PRIME_FACTOR 89017
##  PRIME_FACTOR 434593
##  PRIME_FACTOR 3478697
##  PRIME_FACTOR 49998841
##  PRIME_FACTOR 11927295803
##  PRIME_FACTOR 14064370273
##  PRIME_FACTOR 518069464441
##  PRIME_FACTOR 1858900129817
##  PRIME_FACTOR 161610704597143
##
##  ========================================


> I mean how do I translate x! into proper
> > Python code, so that it will always do the correct math?
>
> Do you want to compute x! (factorial of x)? That is, you want a
> program that given a 4, returns 24?
> Think how would you compute it by hand and try to write the same thing
> using Python instructions.
>
> If you come with a program and have a specific problem someone here
> will be able to help you, but don't expect your homework to be done
> for free...
>
> --
> Gabriel Genellina