Quel est l'algorithme pour trouver des nombres premiers en JavaScript ?

Les nombres premiers sont des entiers positifs qui ne sont divisibles que par 1 et par eux-mêmes. L’algorithme de recherche de nombres premiers est un problème très fondamental et important en informatique. Il peut être appliqué à de nombreux domaines, tels que le cryptage, la compression de données, etc.

En JavaScript, il est très simple d'implémenter l'algorithme de recherche de nombres premiers. Ci-dessous, je présenterai deux méthodes :

1. Méthode de jugement des nombres premiers

Cette méthode est la méthode la plus basique pour trouver des nombres premiers. Son principe est de juger si un entier positif ne peut être divisé que par 1 et par lui-même. La méthode d'implémentation spécifique est la suivante :

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是素数
}

Cette fonction reçoit un entier positif n en paramètre. Si n est un nombre premier, elle renvoie vrai, sinon elle renvoie faux. Sa complexité temporelle est O(n), ce qui n'est pas optimal. Si vous devez juger un grand nombre de nombres premiers, il est recommandé d'utiliser le tamis d'Ératosthène présenté ci-dessous.

2. Tamis d'Eratosthène

Cette méthode supprime les nombres composés à travers une série de tamis, ne laissant que les nombres premiers. La méthode d'implémentation spécifique est la suivante :

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;
}

Cette fonction reçoit un entier positif n en paramètre et renvoie un tableau de nombres premiers inférieurs ou égaux à n. Sa complexité temporelle est O(n log log n), ce qui est plus rapide que la méthode de jugement des nombres premiers.

Conclusion

Ci-dessus sont deux méthodes pour trouver des nombres premiers en JavaScript Bien que la mise en œuvre soit simple, elle est très pratique. Si vous êtes intéressé par les nombres premiers, vous pouvez essayer d’optimiser ces deux méthodes pour les rendre plus rapides et plus efficaces.

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!