Größter Primfaktor einer gegebenen Zahl in Python

Question

Ich bin nicht in der Lage, den folgenden Codeblock zu verstehen, auf dem ich diese Seite selbst gefunden habe. Es erstellt eine Funktion, um den größten Primfaktor einer gegebenen Zahl herauszufinden. Es ist unten angegeben:

def prime_factors(n): 
"""Returns all the prime factors of a positive integer""" 
factors = [] 
d = 2 
while n > 1: 
    while n % d == 0: 
     factors.append(d) 
     n /= d 
    d = d + 1 

return factors 
pfs = prime_factors(1000) 
largest_prime_factor = max(pfs) # The largest element in the prime 

Meine Zweifel, dass die Funktion prime_factors(n) zurückkehren würde die Faktoren von n und nicht der Primfaktoren, da die while-Schleife wird nur überprüft, ob d ein Faktor von n ist und nicht, wenn es auch ein Prime ist, wie es sein sollte.

Bitte weisen Sie darauf hin, wenn ich falsch liege und auch die Gründe hinter Ihrer Logik. Außerdem, wenn ich richtig liege, stellen Sie bitte einen geeigneten Code und die dahinter stehende Logik in einfachen Worten zur Verfügung. Versuchen Sie, den Code so einfach wie möglich zu halten.

Answer 1

Beachten Sie, dass in der inneren Schleife n während der Iteration durch d geteilt wird.

while n % d == 0: 
    factors.append(d) 
    n /= d 

Das heißt, nach jeder Iteration, ist es unmöglich für den neuen Wert von n durch d mehr teilbar zu sein.

Nehmen wir ein Beispiel, sagen wir n = 3000, es hat einen Faktor 15, der keine Primzahl ist. Da jedoch n von d = 3 und d = 5 zuerst geleitet wird, durch die Zeit d15 erreicht, hätte n eine Reihe gewesen, die von 3 noch 5 weder teilbar ist, so dass die nicht-Primfaktors 15 würde nicht n % d == 0 jetzt passieren.

Answer 2

Diese Funktion ist korrekt, achten Sie auf den zweiten While-Block. Es wird die gegebene Zahl fortlaufend durch die d Variable teilen, wenn das Ergebnis der Division einen Rest hat, wird es diesen Block verlassen und d um eins erhöhen, dann wird es wieder laufen.

In diesem Sinne wird diese Funktion die Zahl durch 2 so oft teilen, wie es geht, ohne einen Rest zu hinterlassen, dann wird sie zur nächsten Zahl gehen, die keine Reste übrig lässt. Am Ende wird das Ergebnis nur Primzahlen enthalten.

Es wird so gehen:

def prime_factors(n): 
    factors = [] 
    d=2 
    while n > 1: 
    while n % d == 0: 
     factors.append(d) 
     n /= d 
    d += 1 
    return factors 

print(prime_factors(1000)) # will print [2, 2, 2, 5, 5, 5]