Skip to content

Instantly share code, notes, and snippets.

@dankogai
Last active December 13, 2015 18:58
Show Gist options
  • Save dankogai/4958651 to your computer and use it in GitHub Desktop.
Save dankogai/4958651 to your computer and use it in GitHub Desktop.
How to factor large integers in python

sympy is the module of choice so far

% /opt/local/bin/python2
Python 2.7.3 (default, Oct 23 2012, 00:39:45) 
[GCC 4.2.1 Compatible Apple Clang 4.1 ((tags/Apple/clang-421.11.66))] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from sympy.ntheory import primefactors
>>> primefactors(280671392065546467397265294532969672241810318954163887187279320454220348884327)
[162425297, 215940091, 358456949, 369941863, 479871607, 706170617, 481362815814826159]
>>> 

nzmath barely worked (took several seconds)

% python2
Python 2.7.3 (default, Jan 18 2013, 16:38:53) 
[GCC 4.2.2 20070831 prerelease [FreeBSD]] on freebsd8
Type "help", "copyright", "credits" or "license" for more information.
>>> import nzmath.factor.methods as methods
>>> methods.factor(280671392065546467397265294532969672241810318954163887187279320454220348884327)
[(162425297L, 1), (215940091L, 1), (358456949L, 1), (369941863L, 2), (479871607L, 1), (706170617L, 1), (481362815814826159L, 1)]
>>>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment