Wie kann man in JavaScript effizient feststellen, ob eine Zahl eine Primzahl ist?

Primzahlprüfung in JavaScript

Dieser Artikel befasst sich mit dem Problem, mithilfe von JavaScript festzustellen, ob eine bestimmte Zahl eine Primzahl ist oder nicht. Eine Primzahl ist eine ganze Zahl größer als 1, die durch keine andere natürliche Zahl außer 1 und sich selbst teilbar ist.

Lösung 1

Die traditionelle Methode beinhaltet die Iteration von 2 Berechnen Sie die Quadratwurzel der eingegebenen Zahl und prüfen Sie, ob die Zahl durch eine dieser Zahlen teilbar ist. Wenn ja, ist es keine Primzahl; andernfalls ist es so.

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? (isPrime *= false) : (isPrime *= true);
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

Zeitkomplexität: O(sqrt(n))
Raumkomplexität: O(1)

Lösung 2

Ein alternativer Ansatz nutzt die Tatsache, dass eine Primzahl größer als 2 nicht ungerade sein kann. Es reicht also aus, die Teilbarkeit durch 2 und dann durch ungerade Zahlen bis zur Quadratwurzel der eingegebenen Zahl zu prüfen. Diese Optimierung reduziert die Ausführungszeit erheblich.

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

Zeitkomplexität: O(sqrt(n))
Raumkomplexität: O(1)

Das obige ist der detaillierte Inhalt vonWie kann man in JavaScript effizient feststellen, ob eine Zahl eine Primzahl ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!