azalea says

想当年小学时，质因数分解都是手算滴。现在不同啦，虽然大数的质因数分解是NP问题，不过小一点的数还是可以在有限时间内用计算机算出来的。

方法一：

借用Linux下的factor命令：

azalea@ubuntu:~$ factor 2123324321435364678
2123324321435364678: 2 3 353887386905894113
azalea@ubuntu:~$ factor 31233243214353646789
factor: `31233243214353646789′ is too large

不知道上限到底是多少，不超过19位看来是没问题。

于是python代码可以写成：

>>> import os
>>> def factor(num):
…     stdout = os.popen(’factor %d’%num)
…     s = stdout.read().strip()
…     return map(int, s[s.index(':')+2:].split(’ ‘))
…
>>> factor(28)
[2, 2, 7]

方法二：

使用SymPy, ‘a Python library for symbolic mathematics’.

Ubuntu下直接 sudo apt-get install python-sympy，然后

>>> import sympy
>>> sympy.factorint(2523324321435364678901)
[(31, 1), (107, 1), (760724848186724353L, 1)]
>>> sympy.factorint(3123324321435364678901)

等啊等啊，等了几分钟都没反应。。。看来sympy能搞定21位整数。

以下文章也许和本文有点关系：

• September 25, 2009 -- 一道小学数学题 (28)
• March 6, 2010 -- Don’t do things the hardest way (2)
• February 19, 2010 -- Python统计DNA序列中长度为n的子序列频率 (3)
• January 29, 2010 -- Python语言的诡异特性 (4)
• October 14, 2009 -- 开启IDLE的自动补全功能 (1)