素數因子實施

Question

下面我附上了素數因子分解的代碼，它的工作原理。我只是想知道是否有任何方法可以使輸出更清晰。我將主要因素添加到列表中，但遞歸結束時的最終列表包含列表列表，但我只需要一個包含數字的列表。

def prime_factor(n): 
    list = [] 
    if prime(n)==1: 
     list.append(n) 
     return list 
    else: 
     for i in range(2,n): 
      if n %i ==0: 
       a =prime_factor(i) 
       b = prime_factor(n/i) 
       list.extend(a) 
       list.extend(b) 
       return list 

def prime(n): 
    if n ==2 or n==3: 
     return 1 
    if n==1: 
     return 0 
    for i in range(2,n): 
     if n%i ==0: 
      return 0 
      break 
     if i ==n-1: 
      return 1 
      break 

Answer 1

你可以得到黃金的因素更容易：

def factorize(n): 
    factors = [] 

    p = 2 
    while True: 
     while(n % p == 0 and n > 0): #while we can divide by smaller number, do so 
      factors.append(p) 
      n = n/p 
     p += 1 #p is not necessary prime, but n%p == 0 only for prime numbers 
     if p > n/p: 
      break 
    if n > 1: 
     factors.append(n) 
    return factors 

print factorize(32*9*11*13*13) 

打印

[2，2，2，2，2，3，3，11，13，13]

您的解決方案可以改進爲：

def prime_factor(n): 
    list = [] 
    if n==1: 
     return [1] #or []? 
    else: 
     for i in range(2,n+1): #additional improvement could be made here 
      if n %i ==0: 
       b = prime_factor(n/i) 
       list.append(i) #i is always prime in here, you return once first i is found 
       list.extend(b) 
       return list 

（你的def prime(n):困惑我，這是沒有必要的）