Wie kann man in JavaScript effizient nach Primzahlen suchen?

So bestimmen Sie Primzahlen in JavaScript

In JavaScript ist die Identifizierung von Primzahlen eine häufige Programmieraufgabe. Eine Primzahl ist eine positive ganze Zahl größer als 1, die durch keine andere positive ganze Zahl außer 1 und sich selbst teilbar ist.

Lösung 1: Naiver Ansatz

Der bereitgestellte Code Snippet bietet eine einfache Möglichkeit, zu überprüfen, ob eine Zahl eine Primzahl ist:

<code class="js">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true;

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: Effizienter Ansatz

Ein verbesserter Ansatz zur Überprüfung von Primzahlen ist:

<code class="js">const isPrime = num => {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++) {
    if (num % i === 0) return false;
  }
  return num > 1;
};</code>

Dieser Code macht sich die Tatsache zunutze, dass eine Zahl, die keine Primzahl ist, einen Faktor hat, der kleiner oder gleich ihrer Quadratwurzel ist. Indem wir nach Faktoren bis zur Quadratwurzel suchen, können wir potenzielle Faktoren effizient eliminieren.

Zeitkomplexität: O(sqrt(n))

Raumkomplexität : O(1)

Das obige ist der detaillierte Inhalt vonWie kann man in JavaScript effizient nach Primzahlen suchen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!