So berechnen Sie Primzahlen in Javascript

Primzahlen beziehen sich auf positive ganze Zahlen, die nur durch 1 teilbar sind. Sie sind ein wichtiges Konzept in der Mathematik und werden in der Informatik häufig verwendet. In Javascript können wir die folgenden Methoden verwenden, um Primzahlen zu berechnen.

1. Violent-Enumeration-Methode

Die Violent-Enumeration-Methode ist eine einfache und direkte Methode zur Berechnung von Primzahlen. Wir können bei 2 beginnen und zu n-1 gehen und bestimmen, ob jede ganze Zahl n teilen kann. Wenn es eine ganze Zahl m gibt, die n teilt, dann ist n keine Primzahl. Wenn n nicht durch jede ganze Zahl m teilbar ist, dann ist n eine Primzahl.

Das Folgende ist der Javascript-Implementierungscode der Brute-Force-Aufzählungsmethode:

function isPrime(num) {
  if (num < 2) {
    return false;
  }
  
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  
  return true;
}

2. Sieve of Eratosthenes

Sieve of Eratosthenes ist eine schnellere Methode zur Berechnung von Primzahlen. Seine Grundidee besteht darin, zuerst alle positiven ganzen Zahlen der Reihe nach anzuordnen und dann die Zahlen herauszufiltern, die durch 2 teilbar sind, beginnend mit 2, dann die Zahlen herauszufiltern, die durch 3 teilbar sind, und dann die Zahlen herauszufiltern, die durch 2 teilbar sind um 5 usw., bis keine Primzahlen mehr herausgefiltert werden können.

Das Folgende ist der Javascript-Implementierungscode von Sieve of Eratosthenes:

function sieveOfEratosthenes(n) {
  const primes = new Array(n + 1).fill(true);

  primes[0] = false;
  primes[1] = false;

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.reduce((acc, cur, index) => {
    if (cur) {
      acc.push(index);
    }

    return acc;
  }, []);
}

3. Miller-Rabin-Algorithmus

Miller-Rabin-Algorithmus ist ein probabilistischer Algorithmus zum Testen von Primzahlen, der auf einem wichtigen Satz basiert: wenn n eine Zusammensetzung ist number , dann erfüllt mindestens die Hälfte der positiven ganzen Zahlen a kleiner als n a^(n-1) mod n != 1. Der Kern des Miller-Rabin-Algorithmus besteht darin, k Zufallstests für eine gegebene ganze Zahl n durchzuführen und damit zu bestimmen, ob n eine Primzahl ist. Normalerweise sind nur 15–20 Tests erforderlich, um genauere Ergebnisse zu erhalten.

Das Folgende ist der Javascript-Implementierungscode des Miller-Rabin-Algorithmus:

// 快速幂算法
function powerMod(a, b, m) {
  let res = 1;

  while (b) {
    if (b & 1) {
      res = (res * a) % m;
    }

    a = (a * a) % m;
    b >>= 1;
  }

  return res;
}

function isPrime(num, k) {
  if (num < 2) {
    return false;
  }

  if (num === 2 || num === 3) {
    return true;
  }

  let d = num - 1;
  let r = 0;

  while (d % 2 === 0) {
    d /= 2;
    r++;
  }

  for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (num - 3));
    let x = powerMod(a, d, num);

    if (x === 1 || x === num - 1) {
      continue;
    }

    let flag = false;

    for (let j = 1; j < r; j++) {
      x = (x * x) % num;

      if (x === num - 1) {
        flag = true;
        break;
      }
    }

    if (!flag) {
      return false;
    }
  }

  return true;
}

Die oben genannten sind die drei gängigen Methoden zur Berechnung von Primzahlen in Javascript. Sie können eine geeignete Methode zur Berechnung von Primzahlen in verschiedenen Anwendungsszenarien auswählen.

Das obige ist der detaillierte Inhalt vonSo berechnen Sie Primzahlen in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!