Maison > Article > interface Web > Comment trouver efficacement des nombres premiers dans une plage en JavaScript ?
Trouver efficacement des nombres premiers dans une plage
En JavaScript, l'identification des nombres premiers entre une plage spécifiée peut être réalisée par diverses méthodes. Une approche couramment utilisée est l’algorithme Sieve of Eratosthenes. Cette technique marque les multiples de nombres premiers comme non premiers, permettant une identification efficace des nombres premiers.
Ce qui suit est une implémentation JavaScript d'un algorithme Sieve d'Eratosthène modifié pour trouver des nombres premiers compris entre 0 et 100. :
function getPrimes(max) { var sieve = [], i, j, primes = []; for (i = 2; i <= max; ++i) { if (!sieve[i]) { // i has not been marked -- it is prime primes.push(i); for (j = i << 1; j <= max; j += i) { sieve[j] = true; } } } return primes; }
Dans cette fonction, un tableau nommé « tamis » est utilisé pour suivre les nombres marqués comme non premiers. En parcourant les nombres de 2 au maximum spécifié, les nombres non marqués sont considérés comme premiers et ajoutés au tableau « premiers ». Les multiples de nombres premiers sont ensuite marqués comme non premiers dans le tableau « tamis ».
En utilisant cette fonction, vous pouvez récupérer efficacement tous les nombres premiers dans une plage spécifiée. Par exemple, getPrimes(100) renverra un tableau de tous les nombres premiers compris entre 2 et 100 (inclus).
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!