HOWTO · JavaScript
isPrime in JavaScript
In diesem Tutorial erfahren Sie, wie Sie in JavaScript überprüfen, ob eine Zahl 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).
