Wie können Sie in JavaScript effizient feststellen, ob eine Zahl eine Primzahl ist?

Effiziente Überprüfung von Primzahlen in JavaScript

In der Computerprogrammierung ist die Feststellung, ob eine bestimmte Zahl eine Primzahl ist, eine grundlegende Aufgabe. Eine Primzahl ist eine positive ganze Zahl größer als 1, die außer 1 und sich selbst keine positiven Teiler hat.

Ein beliebter Ansatz zur Prüfung auf Primalität ist das Sieb des Eratosthenes. Aus Leistungsgründen kann jedoch eine effizientere Methode eingesetzt werden, wie in der folgenden JavaScript-Implementierung gezeigt:

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`);

Zeit- und Raumkomplexitätsanalyse

Die Zeit Die Komplexität des obigen Algorithmus beträgt O(sqrt(n)), wobei n den Eingabewert darstellt. Dies liegt daran, dass die Schleife alle Ganzzahlen bis zur Quadratwurzel der Eingabezahl durchläuft, was eine erhebliche Optimierung gegenüber der Prüfung aller Ganzzahlen bis n darstellt.

Die Raumkomplexität beträgt O(1), da keine zusätzlichen Datenstrukturen über primitive Variablen hinaus erforderlich sind.

Alternativer Ansatz

Eine alternative Syntax zur Prüfung der Primalität in JavaScript ist:

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

Dieser Ansatz erreicht die gleiche zeitliche und räumliche Komplexität wie der vorherige und verwendet gleichzeitig eine präzisere Pfeilfunktionssyntax.

Das obige ist der detaillierte Inhalt vonWie können Sie 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!