【求教】用递归的方法求素因子

alexkh

是在《python核心编程》上看到的一个习题：

素因子分解。以刚才练习中的isprime()和getfactors()函数为基础编写一个函数，它接受一个整型作为参数，返回该整型所有素数因子的列表。这个过程叫做求素因子分解，它输出的所有因子之积应该是原来的数字。注意列表里可能有重复的元素。例如输入20，返回的结果应该是[2，2，5]。

我想到了用递归的方法，但老是出错，请各位大牛帮忙看下哪里出了问题，该怎么纠正。多谢了！
代码如下：

1. #coding=utf-8
   
2. 
   
3. def isprime(num):
   
4.     count = num / 2
   
5.     while count >1:
   
6.         if num % count == 0:
   
7.             return False
   
8.             break
   
9.         else:
   
10.             count -= 1
    
11.     else:
    
12.         return True
    
13. 
    
14. def getfactor(num):
    
15.     l = []
    
16.     count = num / 2
    
17.     for n in range(2, count + 1):
    
18.         if num % n == 0 and isprime(n):
    
19.             l.append(n)
    
20.     return l
    
21. 
    
22. def suyinzi(num):
    
23.     fac = getfactor(num)
    
24.     mul = 1
    
25.     for n in fac:
    
26.         mul *= n
    
27.     if mul == num:
    
28.         return fac
    
29.     else:
    
30.         return fac + suyinzi(num / mul)
    
31. 
    
32. print suyinzi(20)
    

复制代码

river_run

楼主你的getfactor函数，在循环前要先对num做素性判断，要不然处理不了素数。

1. 
   
2. def getfactor(num):
   
3.     l = []
   
4.     if isprime(num):
   
5.         return [num]
   
6.     count = num / 2
   
7.     for n in range(2, count + 1):
   
8.         if num % n == 0 and isprime(n):
   
9.             l.append(n)
   
10.     return l
    

复制代码

这样就好了

alexkh

回复 2# river_run


    多谢，确实是这样，之前没考虑明白。