isPrime in JavaScript

Harshit Jindal 12 Oktober 2023
  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
isPrime in JavaScript

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).

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn