Prime因式分解+優化中的遞歸問題

我正在爲任意數字的因子創建模塊。在它裏面，我也有兩個函數（一個導致另一個的調用）發現數字的主要因式分解。Prime因式分解+優化中的遞歸問題

出現的問題是一個遞歸錯誤（如果我的遞歸定義是正確的）。當我爲某個數字調用函數時，它會打印所有素數因子，然後它會添加最後兩個素數因子並再次打印，並重復執行此操作，直至看起來沒有結束。

到目前爲止我的代碼：

def primeFactors(n): 
    from primenum2 import isPrime 
    from math import sqrt 
    global pFact, y 
    x, pFact, y = 2, [], 0 
    if isPrime(n): 
     return n 
    else: 
     while x <= sqrt(n): 
     if isPrime(x) and (n%x==0): 
      pFact.append(x) 
      y = n/x 
      if isPrime(y): 
       pFact.append(y) 
       print pFact 
       break 
      else: 
       primeFactors2(y) 
     else: 
      x += 1 

#NEW FUNCTION - I made two functions to avoid another recursion error that was occuring. 

def primeFactors2(y): 
    from primenum2 import isPrime 
    from math import sqrt 
    z = 2 
    while z <= sqrt(y): 
     if isPrime(z) and (y%z==0): 
     pFact.append(z) 
     y = y/z 
     if isPrime(y): 
      pFact.append(y) 
      print pFact 
      break 
     else: 
      primeFactors2(y) 
     else: 
     z += 1

當我輸入（中殼）：primeFactors(600851475143) < ---這是爲項目歐拉最初

預期輸出（我已經解決了這個問題）： [71, 839, 1471, 6857L]

實際輸出：

[71, 839, 1471, 6857L] 
[71, 839, 1471, 6857L, 1471, 6857L] 
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L] 
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L, 1471, 6857L] 
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L]

它一遍又一遍地將1471和6857L附加到列表中，然後再次打印。然後，它再次添加所有主要因素，然後再次打印。不知道它爲什麼這樣做。任何輸入是不勝感激。另外，如果有什麼方法可以使這個代碼更快/更Pythonic，請告訴我:)謝謝

來源

2012-11-20 Rushy Panchal

不執行'pFact.append（z）'。相反，使一個本地臨時變量'temp = pFact + [z]'。嘗試一下，看看會發生什麼 – inspectorG4dget

當我這樣做並測試了這個函數後，它會打印出[71,6857L]，然後它會輸出6857，再打印一遍。然後加了71和6857，打印出來，然後再次跟着這個循環。 –

我的觀點是「用所有臨時列表替換所有附件」 – inspectorG4dget

你正在做太多的工作。你不需要isPrime或遞歸函數。下面是用於分解整數儘可能簡單的功能的僞代碼，根據審判庭：

define factors(n) 
    f := 2 
    while f * f <= n 
    if n % f == 0 
     output f 
     n := n/f 
    else 
     f := f + 1 
    output n

雖然足夠用於項目歐拉＃3，有更好的方法來因素的整數。準備好之後，我會在我的博客中謙虛地推薦this essay，其中包括此保理算法等，其中包括用五種語言（包括Python）實現的算法。

來源

2012-11-21 00:30:55 user448810

Prime因式分解+優化中的遞歸問題

回答

相關問題