isPrime in JavaScript

1. Naive Lösung zum Überprüfen, ob eine Zahl in JavaScript eine Primzahl ist
2. Quadratwurzellösung zum Überprüfen, ob eine Zahl in JavaScript eine Primzahl ist

Eine Primzahl ist höher als eins mit zwei Faktoren - eins und sich selbst. Das bedeutet, dass Primzahlen immer einen Rest hinterlassen, wenn sie durch andere Zahlen geteilt werden. Die anderen Zahlen größer als eins mit mehr als zwei Teilern heißen zusammengesetzte Zahlen.

In diesem Artikel werden verschiedene Methoden besprochen, um zu überprüfen, ob eine Zahl in JavaScript eine Primzahl ist.

Naive Lösung zum Überprüfen, ob eine Zahl in JavaScript eine Primzahl ist

Der einfachste Weg, um zu überprüfen, ob eine Zahl n eine Primzahl ist, besteht darin, von 2 bis n-1 zu iterieren und dann zu prüfen, ob n durch jede von ihnen teilbar ist.

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= n - 1; i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

Zeitkomplexität

Wir iterieren n-2 Mal von 2 bis n-1. Die Zeitkomplexität dieser Lösung ist O(n).

Raumkomplexität

Die Raumkomplexität dieser Lösung ist O(1).

Quadratwurzellösung zum Überprüfen, ob eine Zahl in JavaScript eine Primzahl ist

Die obige Lösung kann verbessert werden, indem nur bis sqrt(n) iteriert wird. Es basiert auf der Tatsache, dass sqrt(n) * sqrt(n) = n ist, und dass mindestens ein Faktor kleiner als gleich sqrt(n) sein muss. Wenn wir keinen Faktor im Bereich [2, sqrt(n)] finden können, bedeutet dies, dass die Zahl n eine Primzahl ist.

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= Math.sqrt(n); i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

Zeitkomplexität

Da wir die ersten sqrt(n)-Potenzialfaktoren iterieren, ist die Zeitkomplexität der obigen Lösung sqrt(n).

Raumkomplexität

Die Raumkomplexität dieser Lösung ist O(1).