Ein einfaches Faktorisierungsverfahren basiert auf dem Verfahren der Probedivision: Wenn $n$ die vorgegebene natürlich Zahl bezeichnet, dann dividiert man $n$ der Reihe nach durch alle Zahlen von $2$ aufwärts, bis die Division aufgeht oder die $\sqrt{n}$ als Grenze erreicht wird. Wenn auf diese Weise ein Primfaktor gefunden wird, so wird er in einer Liste zur Verwaltung sämtlicher Primfaktoren aufgenommen. Die Ausgangszahl wird durch den gefundenen Primfaktor dividiert und das Verfahren wird mit dem daraus entstehenden Quotienten erneut durchgeführt. Das Verfahren endet, wenn die zu überprüfende Zahl eine Primzahl ist. Diese wird dann ebenfalls in der Liste der Primfaktoren aufgenommen.

Die folgende Übersicht verdeutlicht das Verfahren am Beispiel $n = 51$.

# Übergabe
n = 51
 
# Initialisierung
faktoren = []              {faktoren -> []}
z = n                      {z -> 51}+
 
# Probedivisionen
z % 2 -> 1
z % 3 -> 0
 
# Aktualisierung
p = 3                      {p -> 3}
faktoren = faktoren + [p]  {faktoren -> [3]}
z = z // p                 {z -> 17}
 
# Probedivisionen
z % 2 -> 1
z % 3 -> 2
z % 4 -> 1
z % 5 -> 2
 
# Aktualisierung
p = z                      {p -> 17}
faktoren = faktoren + [p]  {faktoren -> [3, 17]}
z = z // p                 {z -> 1}
 
# Rückgabe
[3, 17]

Allgemein beschreiben lässt sich das Verfahren mit dem folgenden Algorithmus:

ALGORITHMUS primfaktoren(n):
    initialisiere die Liste faktoren: faktoren = []
    initialisiere die Hilfsvariable z: z = n
    SOLANGE z > 1:
        bestimme den kleinsten Primfaktor p von z mit Probedivisionen
        füge p in die Liste faktoren ein
        z = z // p
    Rückgabe: faktoren

Die Processing-Implementierung sieht so aus:

primfaktoren.pde

ArrayList<Long> primfaktoren(long n) {
  ArrayList<Long> faktoren = new ArrayList<Long>();
  long z = n;
 
  while (z > 1) {
    long p = kleinsterPrimfaktor(z);
    faktoren.add(p);
    z = z / p;
  }
 
  return faktoren;
}
 
long kleinsterPrimfaktor(long n) {
  for (long p = 2; p <= sqrt(n); p++) {
    if (n % p == 0) return p;
  }
 
  return n;
}
 
void setup() {
  long[] numbers = new long[] { 11, 42, 48, 51, 100, 101, 221, 585, 1009, 10007 };
 
  for (long number : numbers) {
    println(number, primfaktoren(number));
  }
}
 
void draw() {
}

a) Als Ergebnis berechnet primfaktoren(n) in diesem Fall genau die Faktorenliste [n].

b) $1000000000000000000$ ist schnell zu berechnen, $1000000000000000003$ braucht sehr lange, da es selbst eine Primzahl ist.

primfaktoren_zeit.pde

import java.math.BigInteger;
 
BigInteger TWO = new BigInteger("2");
 
ArrayList<BigInteger> primfaktoren(BigInteger n) {
  ArrayList<BigInteger> faktoren = new ArrayList<BigInteger>();
  BigInteger z = n;
 
  while (z.compareTo(BigInteger.ONE) > 0) {
    BigInteger p = kleinsterPrimfaktor(z);
    faktoren.add(p);
    z = z.divide(p);
  }
 
  return faktoren;
}
 
BigInteger kleinsterPrimfaktor(BigInteger n) {
  for (BigInteger p = TWO; p.compareTo(n.sqrt()) <= 0; p = p.add(BigInteger.ONE)) {
    if (n.mod(p).compareTo(BigInteger.ZERO) == 0) return p;
  }
 
  return n;
}
 
void setup() {
  String[] numbers = new String[] { 
    "11",
    "101",
    "1009",
    "10007",
    "100003",
    "1000003",
    "10000019",
    "100000007",
    "1000000007",
    "10000000019",
    "100000000003",
    "1000000000039",
    "10000000000037",
    "100000000000031",
    "1000000000000037",
    "10000000000000061",
    "100000000000000003",
    "1000000000000000003",
    "10000000000000000051",
    "100000000000000000039",    
    "1000000000000000000117",
    "10000000000000000000009",
    "100000000000000000000117",
    "1000000000000000000000007",
    "10000000000000000000000013",
    "100000000000000000000000067",
    "1000000000000000000000000103",
    "10000000000000000000000000331",
    "100000000000000000000000000319"
  };
 
  for (String number : numbers) {
    long time = System.nanoTime();
    ArrayList<BigInteger> factors = primfaktoren(new BigInteger(number));
    long delta = System.nanoTime() - time;
 
    println(factors, "->", delta / 100_000_000d, "sec.");
  }
}
 
void draw() {
}