Was ist der Algorithmus zum Finden von Primzahlen in JavaScript?

Primzahlen sind positive ganze Zahlen, die nur durch 1 und sich selbst teilbar sind. Der Algorithmus zum Finden von Primzahlen ist ein sehr grundlegendes und wichtiges Problem in der Informatik. Er kann auf viele Bereiche angewendet werden, beispielsweise auf Verschlüsselung, Datenkomprimierung usw.

In JavaScript ist es sehr einfach, den Algorithmus zum Finden von Primzahlen zu implementieren. Im Folgenden werde ich zwei Methoden vorstellen:

1. Methode zur Primzahlbeurteilung

Diese Methode ist die grundlegendste Methode zum Ermitteln von Primzahlen. Ihr Prinzip besteht darin, zu beurteilen, ob eine positive ganze Zahl nur durch 1 und sich selbst geteilt werden kann. Die spezifische Implementierungsmethode lautet wie folgt:

function isPrime(n) {
  if (n <= 1) {
    return false; // 1和0都不是素数
  }

  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false; // 如果n能被i整除，则n不是素数
    }
  }

  return true; // n是素数
}

Diese Funktion empfängt eine positive ganze Zahl n als Parameter. Wenn n eine Primzahl ist, gibt sie true zurück, andernfalls gibt sie false zurück. Seine zeitliche Komplexität beträgt O(n), was nicht optimal ist. Wenn Sie eine große Anzahl von Primzahlen beurteilen müssen, wird empfohlen, das unten vorgestellte Sieb des Eratosthenes zu verwenden.

2. Sieb des Eratosthenes

Diese Methode entfernt zusammengesetzte Zahlen durch eine Reihe von Sieben, sodass nur Primzahlen übrig bleiben. Die spezifische Implementierungsmethode lautet wie folgt:

function getPrimes(n) {
  let arr = new Array(n + 1).fill(true); // 先创建一个全为 true 的数组，代表是素数
  let primes = [];

  for (let i = 2; i <= n; i++) {
    if (arr[i]) {
      primes.push(i); // i 是素数，添加到 primes 数组中
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false; // 将 i 的倍数都标记为不是素数
      }
    }
  }

  return primes;
}

Diese Funktion empfängt eine positive ganze Zahl n als Parameter und gibt ein Array von Primzahlen kleiner oder gleich n zurück. Seine zeitliche Komplexität beträgt O(n log log n), was schneller ist als die Primzahlbeurteilungsmethode.

Fazit

Die oben genannten Methoden zum Finden von Primzahlen in JavaScript sind zwar einfach, aber sehr praktisch. Wenn Sie sich für Primzahlen interessieren, können Sie versuchen, diese beiden Methoden zu optimieren, um sie schneller und effizienter zu machen.

Das obige ist der detaillierte Inhalt vonWas ist der Algorithmus zum Finden von Primzahlen in JavaScript?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!