Wie findet ein Brute-Force-Algorithmus den größten Primfaktor einer Zahl und warum ist er schneller, als jede Zahl zu testen?

Python findet Primfaktoren

Frage:

Zweiteilige Frage:

1. Können Sie erklären, wie ein Brute-Force-Algorithmus zum Finden des größten Primfaktors einer Zahl funktioniert?
2. Warum ist dieser Algorithmus schneller als einer, der einfach jede Zahl testet?

Codebeispiel:

<code class="python">n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)</code>

Antwort:

1. So funktioniert der Algorithmus:

Der gegebene Algorithmus verwendet rohe Gewalt, um den größten Primfaktor zu finden, indem er alle Zahlen von 2 bis zur Quadratwurzel der gegebenen Zahl n iteriert. Für jede Zahl i wird geprüft, ob sie n ohne Rest teilt. Wenn dies der Fall ist, wird n wiederholt durch i dividiert, bis n nicht mehr durch i teilbar ist. Anschließend wird i um 1 erhöht und der Vorgang fortgesetzt. Der größte Primfaktor wird der Endwert von n sein.

2. Warum der Algorithmus schneller ist:

Der angegebene Algorithmus ist schneller als das einfache Testen jeder Zahl, da er die Tatsache ausnutzt, dass jeder Primfaktor einer Zahl kleiner oder gleich ihrer Quadratwurzel ist. Indem der Algorithmus nur bis zur Quadratwurzel von n iteriert, reduziert er die Anzahl potenzieller zu überprüfender Kandidaten und verbessert so seine Effizienz erheblich.

Verbesserter Algorithmus:

Die bereitgestellten Das Codebeispiel weist einige Probleme auf, die verhindern, dass der größte Primfaktor in allen Fällen korrekt ermittelt wird. Eine korrigierte Version des Algorithmus lautet:

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

Dieser Algorithmus findet korrekt den größten Primfaktor, selbst für perfekte Quadrate und Zahlen mit wiederholten Primfaktoren.

Das obige ist der detaillierte Inhalt vonWie findet ein Brute-Force-Algorithmus den größten Primfaktor einer Zahl und warum ist er schneller, als jede Zahl zu testen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!