003 – Suche nach dem größten Primfaktor

 

Die Primfaktoren von 13195 sind 5, 7, 13 und 29.

Was ist der größte Primfaktor von 600851475143?

Lösung

Möglichkeit 1

Sei n die gegebene Zahl. Die einfachste Möglichkeit ist es, nach dem kleinsten Teiler k von n zu suchen, und dann n durch k zu dividieren. Der kleinste Teiler ist auf jeden Fall eine Primzahl (also ein Primfaktor). Anschließend wird erneut nach dem kleinsten Teiler gesucht und durch diesen geteilt. Bei wiederholter Durchführung wird der gefundene Faktor immer größer, da die kleinen Primfaktoren schon herausdividiert sind. n wird schließlich zu 1. Daraus folgt aber auch, dass jeder gefundene Faktor wieder ein Primfaktor sein muss. Es wird der letzte und damit größte gefundene Teiler ausgegeben:

zahl = 600851475143;
max_teiler = 1;

while zahl > 1
    teiler = 2;
    while mod(zahl, teiler) ~= 0
        teiler = teiler + 1;
    end
    zahl = zahl / teiler;
    max_teiler = teiler;
end

max_teiler

Das Ergebnis ist 6857.
Die Rechenzeit beträgt 0.009955 Sekunden.

Möglichkeit 2

Den obigen Algorithmus können wir noch verbessern. 2 ist die einzige gerade Primzahl. Wenn wir 2 getrennt betrachten können wir daher den Teiler in jedem Schritt um 2 erhöhen und somit nur halb so viele Zahlen testen. Wir stellen den Algorithmus außerdem ein wenig um, so dass gleich mehrmals durch den gleichen Faktor geteilt werden kann, ohne dass erneut hochgezählt wird:

zahl = 600851475143;

if mod(zahl, 2) == 0
    max_teiler = 2;
    while mod(zahl, 2) == 0
        zahl = zahl / 2;
    end
else
    max_teiler = 1;
end

teiler = 3;

while zahl > 1
    if mod(zahl, teiler) == 0
        while mod(zahl, teiler) == 0
            zahl = zahl / teiler;
        end
        max_teiler = teiler;
    end
    teiler = teiler + 2;
end

max_teiler

Die Rechenzeit beträgt 0.000259 Sekunden.
Dies ist eine Verbesserung um den Faktor 38.

Möglichkeit 3

Wenn wir eine Zahl mit einem Aufbau wie z.B. 2*1009*[riesige Primzahl] faktorisieren sollen, braucht die Variable “teiler” lange, um zu der Primzahl hochzuzählen. Wir wissen, dass eine Zahl n höchstens einen Primfaktor haben kann, der größer als ihre Wurzel \sqrt{n} ist. Wenn wir mit “teiler” bis zur Wurzel der restlichen Zahl hochgezählt haben, wissen wir also, dass die restliche Zahl eine Primzahl und somit der gesuchte größte Primfaktor ist. Dies ist leicht in das Matlab Programm einzuarbeiten.