Algorithmensammlung: Zahlentheorie: Primfaktorisierung

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Algorithmensammlung: Zahlentheorie

Primfaktorzerlegung[Bearbeiten]

Es gibt Zahlen, die nur durch 1 und sich selbst teilbar sind. Diese werden Primzahlen genannt, z. B. 2, 3, 5, 7, 11... Zahlen, die keine Primzahlen sind, heißen zusammengesetzte Zahlen. Jede zusammengesetzte Zahl lässt sich in Primfaktoren zerlegen, d. h., dass man jede zusammengesetzte Zahl eindeutig als Produkt aus Primzahlen schreiben kann, z. B. . Hier werden Algorithmen vorgestellt, die eine zusammengesetzte Zahl möglichst schnell in ihre Primfaktoren zerlegen.

Laufzeit[Bearbeiten]

Diese ist unterschiedlich, je nach verwendetem Algorithmus. Die Laufzeit des quadratischen Siebes beispielsweise, einer ziemlich komplizierten Faktorisierungsmethode für Zahlen mit weniger als 100 Stellen, ist wahrscheinlich . Die hier zuerst vorgestellten einfachen Methoden liegen aber in einer wesentlich ungünstigeren Ordnung.

Die Laufzeit kann erheblich verringert werden, indem man nur bis zur Quadratwurzel aus n prüft, da eine Zahl nicht als Produkt aus zwei Zahlen dargestellt werden kann, die beide größer als ihre Quadratwurzel sind. Mit der Überprüfung jeweils in Zweierschritten werden die geraden Zahlen ausgespart.

Einfaches Faktorisierungsverfahren[Bearbeiten]

Ein erster Ansatz zur Faktorisierung von n wäre, alle Zahlen kleiner als n daraufhin zu überprüfen, ob sie Teiler von n sind (also ob n modulo der zu prüfenden Zahl 0 ergibt). Dazu bräuchte man n-1 Schritte. Damit kann zwar festgestellt werden, ob n eine Primzahl ist, aber die Primfaktoren können so im Allgemeinen nicht vollständig gewonnen werden. Warum?

  1. Eine Zahl kann mehrfach in der Liste der Primfaktoren auftauchen (z. B. mit der Zwei, die dreimal auftritt).
  2. Außerdem würden so alle Teiler der Zahl ausgegeben und nicht nur die Primfaktoren (4 würde auch als Primfaktor von 8 gekennzeichnet, obwohl 4 eine zusammengesetzte Zahl ist).

Darum ist es notwendig, n durch den gefundenen Teiler so oft wie möglich zu teilen (und damit mehrfach vorkommende Primfaktoren zu registrieren) und mit dem Ergebnis weiterzurechnen (so werden zusammengesetzte Zahlen nicht mehr registriert).

Nun muss das Verfahren noch optimiert werden. Dazu beschränken wir die Überprüfung auf ungerade Zahlen (Ausnahme: 2 selbst), weil gerade Zahlen durch 2 teilbar sind, und brechen den Durchlauf bei ab, weil Zahlen größer als nicht Primfaktoren kleiner als n sein können. Ansonsten gäbe es nämlich noch einen anderen Primfaktor, der kleiner als 2 wäre. Da 2 aber die kleinste Primzahl ist, kann kein Primfaktor größer als sein.

Um alle Teiler von n zu gewinnen, kann man entweder alle Zahlen von 1 bis n auf die Teilereigenschaft überprüfen (und erhält auch die trivialen Teiler 1 und n). Wenn man allerdings mit der Liste aller nicht-trivialen Primfaktoren von n arbeiten möchte, kann man einfach alle Teillisten generieren und für jede generierte Teilliste ihre Elemente multiplizieren. Auf diese Weise besteht das Ergebnis für jede Liste aus einem Teiler von n, weil nur die Primfaktoren von n in maximal der Häufigkeit ihres Vorkommens in der Primfaktorzerlegung von n verwendet wurden.

Implementierungen[Bearbeiten]

Python[Bearbeiten]

Die Funktion bekommt eine natürliche Zahl n größer als 0 übergeben und liefert eine Liste sämtlicher Primfaktoren von n, von 1 und n selbst abgesehen, zurück. Wenn n eine Primzahl ist, wird eine leere Liste zurückgegeben.

# Getestet unter Python 3.4, sollte aber unter allen Python-3.x-Versionen laufen.
# Für Python 2.x ist es evt. erforderlich, den verwendeten Zeichensatz anzugeben.

from itertools import chain


def faktorisiere(n):
    l = []  # Lösungsmenge
    # Auf Teilbarkeit durch 2, und alle ungeraden Zahlen von 3..n/2 testen
    for i in chain([2], range(3, n//2 + 1, 2)):
        # Ein Teiler kann mehrfach vorkommen (z.B. 4 = 2 * 2), deswegen:
        while n % i == 0:
            l.append(i)
            n = n // i  # "//" ist ganzzahlige Division und entspricht int(n/i)
        if i > n:  # Alle Teiler gefunden? Dann Abbruch.
            break
    return l

Wer mit der Deklaration von Zeichensätzen in Python noch nicht so vertraut ist, kann auch die vorkommenden Sonderzeichen (hier vermutlich nur das "ö" in "Lösungsmenge") durch unverfängliche Buchstabenkombinationen (z. B. "oe") ersetzen.
Das oben beschriebene Weiterarbeiten mit dem Divisionsprodukt wurde hier durch eine while-Schleife realisiert. Der Modulo-Operator ist in Python als Prozentzeichen realisiert. Getestet wird bis einschließlich n//2, das +1 dahinter ist aber notwendig, da das Stop-Argument der range()-Funktion, das den Endwert angibt, selbst nicht erreicht wird (bei range(1, n) wird nur bis einschließlich n-1 gezählt).
Die chain()-Funktion kann als Implementierung der Vereinigung von Mengen betrachtet werden.

Weitere Informationen[Bearbeiten]

Die folgenden  Wikipedia-Artikel bieten ausführliche Erläuterungen.