Primzahlen finden – Programmieren lernen mit JavaScript – Thytos
Nächstes Video startet in 3 Sekunden.
Programmieren lernen mit JavaScript

Primzahlen finden

Eine Funk­tion schrei­ben, um Prim­zah­len zu fin­den, klingt kom­pli­ziert, ist aber mit grund­le­gen­den Pro­gram­mier­kennt­nis­sen möglich.

Primzahlen sind Zahlen, die nur durch Eins und sich selbst teilbar sind und darüber hinaus keinen weiteren Teiler besitzen. Sie werden unter anderem in der computerbasierten Kryptographie zum Verschlüsseln von Daten verwendet.

Ziel dieses Artikels ist es, am Ende eine Funktion erstellt zu haben, die alle Primzahlen bis zu einer Obergrenze als Array zurückgibt.
Dabei geht es vor allem um die allgemeine Umsetzung. Der Code muss nicht vollständig auf Effizienz optimiert werden, obwohl auch das in diesem Artikel thematisiert wird.

findPrimes(50);
// => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Aufgabe zerkleinern

Um Aufgaben wie diese in der Programmierung zu lösen, ist es wichtig, zu verstehen, welche Anforderungen erfüllt sein müssen und von welchen Anforderungen diese Anforderungen wiederum abhängen.

Um eine Liste von Primzahlen bis zu einer Obergrenze zurückzugeben, muss zu allererst mal eine Liste erstellt werden, denen die Primzahlen hinzugefügt werden können.

function findPrimes(nr) {
  var res = []; // Liste, der die Primzahlen hinzugefügt werden

  /* Hier werden die Primzahlen gesucht */

  return res; // Liste wird zurückgegeben
}

Um die Primzahlen bis zu einer Obergrenze zu finden, muss jede Zahl bis dahin durchlaufen und überprüft werden, ob sie eine Primzahl ist oder nicht. Wenn sie eine ist, wird sie der Liste an Primzahlen hinzugefügt. Das klingt nach dem Einsatz für eine Schleife.

function findPrimes(nr) {
  var res = [];

  for (var i = 2; i <= nr; i++) { // Laufe von 2 bis nr
    if (/* Falls i eine Primzahl ist */) {
      res[res.length] = i;
    }
  }

  return res;
}

Die Schleife startet erst bei 2, weil 1 keine Primzahl ist und 0 kein Teiler. Sie wird wiederholt, solange i kleiner oder gleich nr ist. Durch das <= wird nr mit in die Schleife eingeschlossen, mit i < nr wäre das nicht der Fall.

Der Code sieht bereits zielführend aus. Was jetzt benötigt wird, ist die Feststellung, ob eine Zahl eine Primzahl ist oder nicht. Das kann als eigene Funktion geschrieben werden.

function isPrime(nr) {
  // Wie kann festgestellt werden, ob
  // eine Zahl Primzahl ist oder nicht?
}

Um festzustellen, ob eine Zahl eine Primzahl ist, wird zuerst ein einfacher Lösungsweg beschritten und anschließend ein etwas effizienterer.

Zuerst muss herausgefunden werden, wie viele Teiler eine Zahl hat. Wenn sie nur Eins und sich selbst als Teiler hat, also zwei insgesamt, dann ist es eine Primzahl.
Dafür wird eine weitere Funktion geschrieben: findFactors, finde Teiler. Wie die findPrimes-Funktion gibt sie eine Liste aller Teiler zurück. Insgesamt funktioniert sie sehr ähnlich zur findPrimes-Funktion, denn auch hier wird mit einer Schleife jede Zahl überprüft, ob sie ein Teiler ist. Für die Prüfung der Teilbarkeit wird der Modulo-Operator verwendet. Damit ist alles gegeben, um die Funktion vollständig zu implementieren.

function findFactors(nr) {
  for (var i = 1, res = []; i <= nr; i++) {
    if (nr % i === 0) {
      res[res.length] = i;
    }
  }
  return res;
}

findFactors(1); // 1 gilt nicht als Primzahl
// => [1]

findFactors(2);
// => [1, 2]

findFactors(3);
// => [1, 3]

findFactors(4);
// => [1, 2, 4]

findFactors(11);
// => [1, 11]

findFactors(12);
// => [1, 2, 3, 4, 6, 12]

Damit kann die isPrime-Funktion nun vervollständigt werden. Die Liste der Teiler wird durch den Aufruf von findPrimes ermittelt. Wenn die Liste exakt zwei Elemente umfasst, ist die Zahl eine Primzahl, ansonsten nicht.

function isPrime(nr) {
  var factors = findFactors(nr); // Liste aller Teiler
  if (factors.length === 2) { // Wenn genau 2 Teiler
    return true; // nr ist Primzahl
  } else {
    return false; // nr ist keine Primzahl
  }
}

isPrime(1);
// => false

isPrime(2);
// => true

isPrime(3);
// => true

isPrime(4);
// => false

isPrime(11);
// => true

isPrime(12);
// => false

Damit funktioniert die Funktion isPrime.

Optimierung von if-Strukturen

An dieser Stelle ist es sinnvoll, auf etwas hinzuweisen: Wann immer es eine if-Struktur in folgendem Aufbau gibt, kann diese zu einer Zeile reduziert werden.

if (/* Bedingung */) {
  return true;
} else {
  return false;
}

Die Bedingung wird bereits als boolscher Wert ausgewertet. Entsprechend ist es redundant, zu schauen, ob etwas true oder false ist, und dann eben true oder false zurückzugeben. Stattdessen kann einfach das Ergebnis der Bedingung zurückgegeben werden.

return /* Bedingung */;

Falls es andersrum ist und true und false umgedreht sind, also im else-Teil erst true zurückgegeben wird, muss einfach die Bedingung mit einem logischen Nicht negiert werden.

if (/* Bedingung */) {
  return false;
} else {
  return true;
}

// Entspricht

return !(/* Bedingung */); // Negation von Bedingung

Damit kann die isPrime-Funktion vereinfacht werden.

function isPrime(nr) {
  // Auf eine Zeile reduziert
  return findFactors(nr).length === 2;
}

Mit der funktionierenden isPrime-Funktion kann auch findPrimes vervollständigt werden.

function findPrimes(nr) {
  for (var i = 2, res = []; i <= nr; i++) {
    if (isPrime(i)) { // Einsatz von isPrime
      res[res.length] = i;
    }
  }
  return res;
}

findPrimes(10)
// => [2, 3, 5, 7]

findPrimes(50)
// => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Optimierung

Die Funktion findPrimes gibt nun erfolgreich alle Primzahlen bis zu einer Obergrenze zurück. Sie kann allerdings noch optimiert werden.
Die Funktion isPrime ermittelt mit findFactors eine Liste aller Teiler einer Zahl, bevor sie daraufhin feststellt, ob die Zahl eine Primzahl ist oder nicht. Welche Teiler eine Zahl alle hat, ist für die Feststellung ihrer Primzahl-Eigenschaft aber völlig irrelevant. Stattdessen reicht es aus, zu ermitteln, ob eine Zahl irgendeinen Teiler außer Eins und sich selbst hat.
Dazu wird der Schleifendurchlauf in isPrime implementiert und die Funktion kann false zurückgeben, sobald ein Teiler zwischen Eins und der Zahl gefunden wird. Die Zahl wird isPrime2 genannt, um sich von der ersten zu unterscheiden.

function isPrime2(nr) {
  for (var i = 2; i < nr; i++) {
    // Die Schleife beginnt bei 2, weil 1 eh immer ein Teiler ist
    // Die Schleife wird bei nr - 1 beendet, weil nr eh immer ein Teiler ist
    // Wenn zwischen 1 und der Zahl irgendein Teiler gefunden wird,
    // ist die Zahl keine Primzahl
    if (nr % i === 0) {
      // An dieser Stelle ist nr durch i teilbar
      // Deswegen kann isPrime2 hier beendet werden
      return false; // nr ist keine Primzahl
    }
  }
  // Wenn die Funktion bis hierhin durchlaufen wird, heißt das,
  // dass sie innerhalb der Schleife nicht durch return beendet
  // wurde. D.h. kein Teiler konnte ermittelt werden => Die Zahl
  // ist eine Primzahl
  return true;
}


isPrime2(2);
// => true

isPrime2(3);
// => true

isPrime2(4);
// => false

isPrime2(11);
// => true

isPrime2(12);
// => false

isPrime2 liefert die richtigen Ergebnisse zurück und ist dabei wesentlich effizienter, weil nicht alle Teiler ermittelt und in einer Liste erfasst werden.
Ein falsches Ergebnis gibt es jedoch bei der Zahl Eins.

isPrime2(1);
// => true

Weil die Schleife erst mit 2 beginnt, wird sie im Fall von 1 gar nicht erst ausgeführt. Für 1 sollte deswegen ein Sonderfall implementiert werden.

function isPrime2(nr) {
  if (nr === 1) return false; // Sonderfall für 1
  for (var i = 2; i < nr; i++) {
    if (nr % i === 0) {
      return false;
    }
  }
  return true;
}

isPrime2(1)
// => false

findPrimes wird nun als findPrimes2 implementiert und nutzt die isPrime2-Funktion.

function findPrimes2(nr) { // findPrimes2
  for (var i = 2, res = []; i <= nr; i++) {
    if (isPrime2(i)) { // isPrime2 statt isPrime
      res[res.length] = i;
    }
  }

  return res;
}

findPrimes2(50);
// => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

In einem stichprobenhaften Vergleich wird die Effizienzsteigerung deutlich.

Funktionsaufruf Dauer der Ausführung
findPrimes(100000) 28,111 s
findPrimes2(100000) 2,596 s

Die zweite Funktion ist rund zehnmal schneller als die erste. Das zeigt eine wichtige Erkenntnis über Schleifen und Funktionen: Wie viele Anweisungen ausgeführt werden, ist nicht so ersichtlich wie beim manuellen Aufruf von Anweisungen. Dadurch kann es passieren, dass unnötiger Code ausgeführt wird, ohne dass es auffällt. Beispielsweise, indem eine Schleife einmal öfter durchlaufen wird als es sein müsste; oder mehr Daten verarbeitet werden, als nötig wären. Wenn eine Prozedur dann, wie in der Tabelle oben, hunderttausendmal ausgeführt wird oder noch öfter, kann Ineffizienz zum Problem werden.

Auch findPrimes2 ist nicht die effizienteste Lösung zum Finden von Primzahlen. Es soll vielmehr als Beispiel dienen, sich über die Qualität von Lösungsstrategien Gedanken zu machen.