Python 将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。

时间:2024-11-08 19:36:33

遇到一个python编程联系题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。


版本一:

开始,没动脑子就开始写了,结果如下代码

#! /usr/bin/python
# 
import math
number = int(raw_input("Enter a number: "))

while number != 1:

    for i in range(1, number + 1):
        if (number % i) == 0 and i != 1:
            number = number / i
            if number == 1:
                print " %d" %i
            else:
                print " %d*" %i,
            break
结果,输入9876543210这个十位数的时候,报错:
Traceback (most recent call last):
  File "./", line 8, in <module>
    for i in range(1, number + 1):
OverflowError: range() result has too many items



版本二:

版本一报错是因为range有了太多的项,于是想着减少range出的list的项。由于,在判断一个数n是否是质数的时候,只需从2到n的平方根就行了,所以有了版本二,代码如下:

#! /usr/bin/python
# 014_1.py
import math
number = int(raw_input("Enter a number: "))

list = []

def getChildren(num):
    print '*'*30
    isZhishu = True
    for i in range(2, int((1 + num)) + 1): #多加个1
        if num % i == 0 and i != num :
            (i)
            isZhishu = False
            getChildren(num / i)
            break
    
    if isZhishu:
        (num)
getChildren(number)
print list

这样,数字可以增大很多而不至于报错。但是 ,也是很有限度的,当输入大数如 123124324324134334 时,会导致内存不足,杀死进程

Traceback (most recent call last):
  File "./014_1.py", line 20, in <module                                            >
    getChildren(number)
  File "./014_1.py", line 11, in getChildren
    for i in range(2, int((1 +  num)) + 1):
MemoryError



为了追求能对更大的数进行操作,猜想原因可能是递归调用时每次都需要建立一个很大的由range()建立的list,于是想避免range的使用,于是有了版本三:

版本三:

代码

#! /usr/bin/python
# 014_1.py
import math
number = int(raw_input("Enter a number: "))

list = []

def getChildren(num):
    print '*'*30
    isZhishu = True
    i = 2
    square = int((num)) + 1
    while i <= square:
        if num % i == 0:
            (i)
            isZhishu = False
            getChildren(num / i)
            i += 1
            break
        i += 1
    if isZhishu:
        (num)

getChildren(number)
print list

同样对123124324324134334 进行操作,速度很快,得到如下结果


 Enter a number: 123124324324134334
******************************
******************************
******************************
******************************
******************************
[2, 293, 313, 362107, 1853809L]



由于初学python,不知道在使用range()时是否真的需要建立一个list在那,不过版本三避免了list的建立,效果也确实好了很多。打印的**************************是当时测试的代码。

有什么错误和不好的地方,请指出,多谢指教