Programma ricorsivo Python per prime fattorizzare un numero

Question

Ho scritto il seguente programma per scomporre in fattori primi un numero:

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

Di seguito è l'output che ottengo:

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

Altho ', il valore restituito viene stampato correttamente, il valore restituito dopo sembra non stamparne nessuno, sempre. Cosa mi sto perdendo?

Inoltre, come posso migliorare il programma (continuando a utilizzare la ricorsione)

Answer 1

La tua funzione prime_factorize non ha un'istruzione return nel caso ricorsivo: vuoi invocare " return prime_factorize (x / i, li) " sull'ultima riga. Provalo con un numero primo (quindi non è necessaria la chiamata ricorsiva) per vedere che funziona in quel caso.

Probabilmente vuoi anche rendere la firma simile a:

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

altrimenti si ottengono risultati errati quando lo si chiama due o più volte:

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

Answer 2

Se vuoi farlo completamente ricorsivo, consiglierei questo codice, restituisce la risposta corretta e il modo in cui funziona è abbastanza chiaro. Se vuoi rendere il programma il più efficiente possibile, ti consiglio di attenerti a uno dei tuoi metodi precedenti.

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

Questo è un modo completamente ricorsivo per risolvere il tuo problema

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

Answer 3

@ Anthony ha risposto correttamente alla tua domanda originale su print . Tuttavia, nello spirito dei numerosi suggerimenti che sono stati offerti, ecco una semplice rifattorizzazione usando la rimozione della ricorsione della coda:

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

Questo non affronta i problemi di prestazioni cruciali (il comportamento big-O è lo stesso della soluzione originale), ma poiché Python stesso non esegue l'ottimizzazione della ricorsione della coda, è importante imparare a farlo manualmente.

" Cambia i passaggi ricorsivi [non-case-case 'return thisfun (newargs)' in args = newargs; continua e metti l'intero corpo in un mentre True: loop " è l'idea di base dell'ottimizzazione della ricorsione della coda. Qui ho anche reso li un non-arg (nessun motivo per essere un arg), ho messo una condizione sul while , ed ho evitato il continue dal momento che il ricorsivo il passo era comunque alla fine del corpo.

Questa formulazione sarebbe una buona base da cui applicare ulteriori refactoring ottimizzati (evitamento sqrt, memoization, ...) per raggiungere prestazioni migliori.

Answer 4

Una versione più funzionale.

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

va bene.