Comment calculer les nombres premiers en javascript

Les nombres premiers font référence à des entiers positifs qui ne peuvent être divisés que par 1 et eux-mêmes. Ils constituent un concept important en mathématiques et sont largement utilisés en informatique. En Javascript, nous pouvons utiliser les méthodes suivantes pour calculer les nombres premiers.

1. Méthode d'énumération violente

La méthode d'énumération violente est une méthode simple et directe de calcul des nombres premiers. Nous pouvons partir de 2 et passer à n-1, et déterminer si chaque entier peut diviser n. S’il existe un entier m qui divise n, alors n n’est pas premier. Si n n’est pas divisible par tout entier m, alors n est un nombre premier.

Ce qui suit est le code d'implémentation Javascript de la méthode d'énumération par force brute :

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

2. Le tamis d'Eratosthène

Le tamis d'Eratosthène est un moyen plus rapide de calculer les nombres premiers. Son idée de base est d'abord de classer tous les entiers positifs dans l'ordre, puis de filtrer les nombres pouvant être divisés par 2 en commençant par 2, puis de filtrer les nombres pouvant être divisés par 3, puis de filtrer les nombres pouvant être divisés. par 5, et ainsi de suite, jusqu'à ce qu'aucun nombre premier ne puisse plus être filtré.

Ce qui suit est le code d'implémentation Javascript du Tamis d'Ératosthène :

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. Algorithme de Miller-Rabin

L'algorithme de Miller-Rabin est un algorithme de test probabiliste de nombres premiers, basé sur un théorème important : si n est un composé nombre , alors au moins la moitié des entiers positifs a inférieurs à n satisfont a^(n-1) mod n != 1. Le cœur de l’algorithme de Miller-Rabin est d’effectuer k tests aléatoires pour un entier n donné et de l’utiliser pour déterminer si n est un nombre premier. Normalement, seuls 15 à 20 tests sont nécessaires pour obtenir des résultats plus précis.

Ce qui suit est le code d'implémentation Javascript de l'algorithme de Miller-Rabin :

// 快速幂算法
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;
}

Voici les trois méthodes courantes de calcul des nombres premiers en Javascript. Vous pouvez choisir une méthode appropriée pour calculer les nombres premiers dans différents scénarios d'application.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!