How to factor using Python?

Mensanator mensanator at aol.com
Tue Mar 11 02:17:11 CET 2008


On Mar 10, 6:32 pm, Nathan Pinno <MadComputer... at gmail.com> wrote:
> On Mar 10, 12:10 pm, Mensanator <mensana... at aol.com> wrote:
>
>
>
>
>
> > 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:
>
> > 508184298003433059930221143303110332712493139579190463526792062622045893426­23811236647989889145173098650749
>
> > 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',
> > '50818429800343305993022114330311033271249313957919046352679206262204589342­623811236647989889145173098650749']
> > ##
> > ##  ['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
>
> Thanks on the factoring bit, but I did mean factorial, not factoring.
> How do I code that correctly, so that I can figure the following
> equation out: cos(Pi * (z-1)! / z). Python returns a invalid syntax
> error and highlight the !.

Because Python doesn't support the factorial operator.

> So it would be nice to find a way to solve
> such a problem.

Instead of using MIRACL which doesn't have a Python interface,
you could instaed get the GMP library which DOES have a Python
interface (Google for gmpy, make sure to get the version that
matches your Python version).

Then you can do gmpy.fac(z-1) to get the factorial.

or

>>> import math
>>> import gmpy
>>> a = math.cos(gmpy.pi(0)*gmpy.fac(4-1)/4)
>>> print a
-1.83690953073e-016



>
> Thanks,
> Nathan P.- Hide quoted text -
>
> - Show quoted text -




More information about the Python-list mailing list