Algorithmensammlung: Zahlentheorie: Primfaktorisierung

Primfaktorzerlegung

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. $91=7\cdot 13$ . Hier werden Algorithmen vorgestellt, die eine zusammengesetzte Zahl möglichst schnell in ihre Primfaktoren zerlegen.

Laufzeit

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 $\exp \left({\sqrt {\ln n\cdot \ln \ln n}}\right)$ . 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

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?

Eine Zahl kann mehrfach in der Liste der Primfaktoren auftauchen (z. B. $8=2\cdot 2\cdot 2$ mit der Zwei, die dreimal auftritt).
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 ${\sqrt {n}}\$ ab, weil Zahlen, die einen größeren Primfaktor haben, auch mindestens einen kleineren haben, und der größere durch Division von $n$ durch alle kleineren Primfaktoren bestimmt werden kann.

Implementierungen

Pseudocode

Es wird vorausgesetzt, dass n eine natürliche Zahl ist (größer als 0).

function primfaktoren (n)
  f ← Leere Liste
  if n = 1 then return f
  t ← 2
  while t * t ≤ n do
    begin
    while n mod t = 0 do
      begin
      Füge t zur Liste f hinzu
      n ← n / t
      end
    t ← t + 1
    end
  Füge n zur Liste f hinzu
  return f

Java

import java.util.*;

// Zerlegung in Primfaktoren:
// n ... Gegebene Zahl (natürlich)
  
public static Vector<Long> primfaktoren (long n) {
  Vector<Long> f = new Vector<Long>();
  if (n == 1) return f;
  long t = 2;
  while (t*t <= n) {
    while (n%t == 0) {
      f.add(t); 
      n /= t;
      }
    t++;
    }
  f.add(n);
  return f;
}

Python

Die Funktion bekommt eine natürliche Zahl n größer als 0 übergeben und liefert eine Liste sämtlicher Primfaktoren von n zurück.

# Getestet unter Python 3.6, 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):
    if n == 0: return     # verhindert Endlosschleife 
    l = []  # Lösungsmenge
    # Auf Teilbarkeit durch 2, und alle ungeraden Zahlen von 3..sqrt(n) 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*i > n:  # Alle Teiler gefunden? Dann Abbruch.
            if n > 1:
                l.append (n)
            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). Allerdings wird die Schleife immer vorher abgebrochen, weil alle Primfaktoren gefunden wurden; es muss nur bis einschließlich i = sqrt(n), also i*i <= n, getestet werden; das nach der Division durch alle gefundenen Primfaktoren verbleibende n ist dann der letzte Faktor.
Die chain()-Funktion kann als Implementierung der Vereinigung von Mengen betrachtet werden.

Weitere Informationen

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