Python实现将一个正整数分解质因数的方法分析
本文实例讲述了Python实现将一个正整数分解质因数的方法。分享给大家供大家参考，具体如下：
遇到一个python编程联系题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
版本一：
开始，没动脑子就开始写了，结果如下代码
#!/usr/bin/python
#014.py
importmath
number=int(raw_input("Enteranumber:"))
whilenumber!=1:
foriinrange(1,number+1):
if(number%i)==0andi!=1:
number=number/i
ifnumber==1:
print"%d"%i
else:
print"%d*"%i,
break
结果，输入9876543210这个十位数的时候，报错：
Traceback(mostrecentcalllast):
File"./014.py",line8,in
foriinrange(1,number+1):
OverflowError:range()resulthastoomanyitems
版本二：
版本一报错是因为range有了太多的项，于是想着减少range出的list的项。由于，在判断一个数n是否是质数的时候，只需从2到n的平方根就行了，所以有了版本二，代码如下：
#!/usr/bin/python
#014_1.py
importmath
number=int(raw_input("Enteranumber:"))
list=[]
defgetChildren(num):
print'*'*30
isZhishu=True
foriinrange(2,int(math.sqrt(1+num))+1):#多加个1
ifnum%i==0andi!=num:
list.append(i)
isZhishu=False
getChildren(num/i)
break
ifisZhishu:
list.append(num)
getChildren(number)
printlist
这样，数字可以增大很多而不至于报错。但是，也是很有限度的，当输入大数如123124324324134334时，会导致内存不足，杀死进程
Traceback(mostrecentcalllast):
File"./014_1.py",line20,in
getChildren(number)
File"./014_1.py",line11,ingetChildren
foriinrange(2,int(math.sqrt(1+ num))+1):
MemoryError
为了追求能对更大的数进行操作，猜想原因可能是递归调用时每次都需要建立一个很大的由range()建立的list，于是想避免range的使用，于是有了版本三：
版本三：
代码
#!/usr/bin/python
#014_1.py
importmath
number=int(raw_input("Enteranumber:"))
list=[]
defgetChildren(num):
print'*'*30
isZhishu=True
i=2
square=int(math.sqrt(num))+1
whilei<=square:
ifnum%i==0:
list.append(i)
isZhishu=False
getChildren(num/i)
i+=1
break
i+=1
ifisZhishu:
list.append(num)
getChildren(number)
printlist
同样对123124324324134334进行操作，速度很快，得到如下结果
Enteranumber:123124324324134334
******************************
******************************
******************************
******************************
******************************
[2,293,313,362107,1853809L]
PS：这里再为大家推荐几款计算工具供大家进一步参考借鉴：
在线