Wie können Sie den Brute-Force-Algorithmus zum Finden von Primfaktoren in Python optimieren?

Primfaktoren in Python finden: Ein umfassender Leitfaden

Die Bestimmung von Primfaktoren ist eine grundlegende Aufgabe in der Zahlentheorie. Ein Ansatz zur Ermittlung des größten Primfaktors sind Brute-Force-Algorithmen. Allerdings sind nicht alle Algorithmen gleich.

Brute-Force-Algorithmus

Ein häufig verwendeter Algorithmus besteht darin, Zahlen inkrementell zu testen, bis eine Zahl gefunden wird, die sich gleichmäßig in das Original aufteilt Nummer. Betrachten wir einen Beispielcode:

n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)

Dieser Code sucht nach dem größten Primfaktor von 600851475143. Allerdings ist er ineffizient und dauert etwa 0,01 Sekunden.

Optimiert Brute-Force-Algorithmus

Eine verbesserte Version des Brute-Force-Algorithmus kann die Laufzeit deutlich reduzieren:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Dieser Algorithmus terminiert, sobald i die Quadratwurzel von n überschreitet , wodurch das Testen vieler unnötiger Zahlen effektiv entfällt. Dadurch wird die Laufzeit drastisch verkürzt und dauert für die gleiche Eingabe etwa 388 Mikrosekunden.

Vollständige Primfaktorzerlegung

Wenn das Ziel darin besteht, die vollständige Primzahl zu erhalten Für die Faktorisierung einer Zahl ist eine geringfügige Änderung des Algorithmus erforderlich:

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

Dieser Algorithmus verwaltet eine Liste namens „Faktoren“, in der die gefundenen Primfaktoren gespeichert werden. Wenn n am Ende größer als 1 ist, gibt es den endgültigen Primfaktor an, der dann zur Liste hinzugefügt wird.

Zusammenfassend lässt sich sagen, dass die Wahl eines effizienten Primfaktorisierungsalgorithmus entscheidend für die Leistung ist. Der optimierte Brute-Force-Algorithmus sorgt für eine deutliche Geschwindigkeitsverbesserung, während der vollständige Faktorisierungsalgorithmus die vollständige Primfaktorzerlegung einer gegebenen Zahl bietet.

Das obige ist der detaillierte Inhalt vonWie können Sie den Brute-Force-Algorithmus zum Finden von Primfaktoren in Python optimieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!