How to factor using Python?

[Nathan Pinno]

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:
>
> 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

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 !. So it would be nice to find a way to solve
such a problem.

Thanks,
Nathan P.