用python进行质因数分解
Apr 15, 2009想当年小学时,质因数分解都是手算滴。现在不同啦,虽然大数的质因数分解是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位整数。