Wie finde ich den größten Primfaktor einer Zahl in Python?

Primfaktoren in Python finden

Eine häufige Aufgabe in der Zahlentheorie besteht darin, die Primfaktoren einer Zahl zu finden. Eine mögliche Methode besteht darin, die Zahl einfach durch jede zweite Zahl von 2 bis zum Boden ihrer Quadratwurzel zu dividieren und zu prüfen, ob der Rest 0 ist. Allerdings kann dieser Ansatz rechenintensiv sein.

Eine effizientere Brute- Nachfolgend wird ein Force-Algorithmus speziell zum Finden des größten Primfaktors einer Zahl vorgestellt:

<code class="python">def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Dieser Algorithmus iteriert durch alle Zahlen bis zur Quadratwurzel der gegebenen Zahl. Für jede Zahl wird geprüft, ob die Zahl ein Faktor der angegebenen Zahl ist, und die Zahl wird durch den Faktor dividiert, wenn dies der Fall ist. Der Algorithmus wird fortgesetzt, bis die Zahl nicht mehr durch eine der Zahlen im Bereich teilbar ist und die verbleibende Zahl der größte Primfaktor ist.

<code class="python">largest_prime_factor(600851475143)
# Output: 6857

Alternativ zum Finden aller Primfaktoren einer Zahl:

<code class="python">def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors</code>

Das obige ist der detaillierte Inhalt vonWie finde ich den größten Primfaktor einer Zahl in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!