Python rekursive Programm prime factorize eine Reihe

Question

Ich schrieb das folgende Programm zu prime factorize eine Zahl:

import math
def prime_factorize(x,li=[]):
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
        if not x%i:
            li.append(i)
            break
    else:                      #This else belongs to for
        li.append(x)
        print li               #First print statement; This is what is returned
        return li
    prime_factorize(x/i,li)

if __name__=='__main__':
    print prime_factorize(300)   #Second print statement, WTF. why is this None

Im Anschluss an die Ausgabe erhalte ich:

 [2, 2, 3, 5, 5]
 None

Altho‘, der zurückgegebene Wert richtig gedruckt wird, scheint der nach Rückgabewert keiner zu drucken, die ganze Zeit. Was bin ich?

Auch, wie kann ich das Programm verbessern (Fortsetzung die Rekursion verwenden)

Answer 1

Ihre prime_factorize Funktion hat keine return-Anweisung in der rekursiven Fall - Sie wollen „return prime_factorize (x / i, li)“ auf seiner letzten Zeile aufzurufen. Versuchen Sie es mit einer Primzahl (so der rekursive Aufruf ist nicht erforderlich), um zu sehen, dass es in diesem Fall funktioniert.

Auch möchten Sie wahrscheinlich die Signatur etwas machen, wie:

def prime_factorize(x,li=None):
    if li is None: li = []

sonst erhalten Sie falsche Ergebnisse, wenn es zwei oder mehrere Male aufrufen:

>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]

Answer 2

Wenn Sie es vollständig rekursiv tun wollen, würde ich diesen Code empfehlen, tut es die richtige Antwort zurückgeben und die Art, wie es funktioniert, ist ziemlich klar. Wenn Sie das Programm so effizient wie möglich machen wollen, würde ich empfehlen, Sie zu einem Ihrer bisherigen Methoden zu bleiben.

def primeFact (i, f):
    if i < f:
        return []
    if i % f == 0:
        return [f] + primeFact (i / f, 2)
    return primeFact (i, f + 1)

Dies ist eine völlig rekursive Art und Weise Ihr Problem zu lösen

>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]

Answer 3

@ Anthony richtig Ihre ursprüngliche Frage zu print beantwortet. Doch im Geist der einige Tipps, die auch angeboten wurden, ist hier eine einfache Refaktorisierung mit Endrekursion Entfernung:

def prime_factorize(x):
  li = []
  while x >= 2:
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
      if not x%i:
        li.append(i)
        break
    else:
      li.append(x)
      return li
    x //= i

Dies bezieht sich nicht auf die entscheidenden Leistungsprobleme (big-O-Verhalten ist die gleiche wie für Ihre ursprüngliche Lösung) - aber da Python selbst Schwanz-Rekursion Optimierung nicht tun, ist es wichtig, um es manuell zu lernen, zu tun.

„Ändern Sie die [Nicht-Basis-Fall] rekursiven Schritte 'return thisfun(newargs)' in args=newargs; continue und legte den ganzen Körper in eine while True: Schleife“ ist die Grundidee der Schwanz-Rekursion Optimierung. Hier habe ich auch ein nicht-arg gemacht li (kein Grund dafür ein arg zu sein), setzen Sie einen Zustand auf dem while und vermied den continue da der rekursive Schritt am Ende des Körpers ohnehin war.

Diese Formulierung wäre eine gute Basis, um gelten weiter zu optimieren Refactorings (sqrt Vermeidung, memoization, ...) in Richtung einer besseren Leistung zu erreichen.

Answer 4

Eine funktionelle Stil Version.

def prime_factorize( number ):
    def recurse( factors, x, n ):
        if x<2: return factors # 0,1 dont have prime factors
        if n > 1+x**0.5: # reached the upper limit
            factors.append( x ) # the only prime left is x itself
            return factors
        if x%n==0: # x is a factor
            factors.append( n )
            return recurse( factors, x/n, n )
        else:
            return recurse( factors, x, n+1 )
    return recurse( [], number, 2)

for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
    assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
    #print num, ":", factors

Answer 5

def primeFactorization(n):
    """ Return the prime factors of the given number. """
    factors = []
    lastresult = n
    while 1:
        if lastresult == 1:
            break

        c = 2

        while 1:
            if lastresult % c == 0:
                break

            c += 1

        factors.append(c)
        lastresult /= c

    return factors

ist es in Ordnung.