Programme JavaScript pour compter les nombres premiers dans une plage

Un nombre premier est un nombre qui a exactement deux diviseurs parfaits. Nous verrons deux manières de trouver le nombre de nombres premiers dans une plage donnée. La première consiste à utiliser une méthode de force brute, qui présente une complexité temporelle assez élevée. Nous améliorerons ensuite cette méthode et adopterons l'algorithme Sieve d'Eratosthène pour avoir une meilleure complexité temporelle. Dans cet article, nous trouverons le nombre total de nombres premiers dans une plage donnée à l'aide du langage de programmation JavaScript.

Loi violente

Tout d'abord, dans cette méthode, nous apprendrons comment déterminer si un nombre est premier ou non, nous pouvons le trouver de deux manières. Une méthode a une complexité temporelle O(N) et l’autre méthode a une complexité temporelle O(sqrt(N)).

Méthode directe pour déterminer si un nombre est premier

Exemple

Tout d'abord, nous allons effectuer une boucle for jusqu'à obtenir un nombre, et compter les nombres qui peuvent diviser le nombre. Si le nombre qui peut diviser le nombre n'est pas égal à 2, alors le nombre n'est pas un nombre premier, sinon le nombre est premier. le nombre est un nombre premier. Regardons le code -

function isPrime(number){
   var count = 0;
   for(var i = 1;i<=number;i++)    {
      if(number%i == 0){
         count = count + 1;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}

// checking if 13 and 14 are prime numbers or not 
if(isPrime(13)){
   console.log("13 is the Prime number");
}
else{    
   console.log("13 is not a Prime number")
}

if(isPrime(14)){
   console.log("14 is the Prime number");
}
else{
   console.log("14 is not a Prime number")
}

Dans le code ci-dessus, nous passons de 1 à nombre, trouvons le nombre dans la plage de nombres qui peut diviser le nombre donné, et obtenons combien de nombres peuvent diviser le nombre donné, et imprimons le résultat sur cette base.

La complexité temporelle du code ci-dessus est O(N), vérifier si chaque nombre est premier coûtera O(N*N), ce qui signifie que ce n'est pas un bon moyen de vérifier.

Méthodes mathématiques

Nous savons que lorsqu'un nombre divise complètement un autre nombre, le quotient est également un entier parfait, c'est-à-dire que si un nombre p peut être divisé par un nombre q, le quotient est r, c'est-à-dire q * r = p. r divise également le nombre p par le quotient q. Cela signifie donc que les diviseurs parfaits viennent toujours par paires.

Exemple

Grâce à la discussion ci-dessus, nous pouvons conclure que si nous vérifions uniquement la division par la racine carrée de N, cela donnera le même résultat en très peu de temps. Voyons le code de la méthode ci-dessus -

function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i<=number;i++){
      if(number%i == 0){
         count = count + 2;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}
// checking if 67 and 99 are prime numbers or not 
if(isPrime(67)){
   console.log("67 is the Prime number");
}
else{
   console.log("67 is not a Prime number")
}
if(isPrime(99)){
   console.log("99 is the Prime number");
}
else{
   console.log("99 is not a Prime number")
}

Dans le code ci-dessus, nous venons de changer le code précédent en changeant la portée de la boucle for, car désormais elle ne vérifiera que la première racine carrée de N éléments, et nous avons augmenté le nombre de 2.

La complexité temporelle du code ci-dessus est O(sqrt(N)), ce qui est mieux, ce qui signifie que nous pouvons utiliser cette méthode pour trouver le nombre de nombres premiers qui existent dans une plage donnée.

Le nombre de nombres premiers compris entre L et R

Exemple

Nous allons implémenter le code précédemment donné dans une plage et compter le nombre de nombres premiers dans une plage donnée. Implémentons le code -

function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i<=number;i++)    {
      if(number%i == 0){
         count = count + 2;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}
var L = 10
var R = 5000
var count = 0
for(var i = L; i <= R; i++){
   if(isPrime(i)){
      count = count + 1;
   }
}
console.log(" The number of Prime Numbers in the given Range is: " + count);

Dans le code ci-dessus, nous parcourons la plage de L à R en utilisant une boucle for, et à chaque itération, nous vérifions si le nombre actuel est premier. Si le nombre est premier, alors nous incrémentons le compte et enfin imprimons la valeur.

La complexité temporelle du code ci-dessus est O(N*N), où N est le nombre d'éléments dans Range.

Criblage par l'algorithme Eratosthène

Exemple

L'algorithme Sieve d'Eratosthène fonctionne très efficacement et peut trouver le nombre de nombres premiers dans une plage donnée en un temps O(Nlog(log(N))) Par rapport à d'autres algorithmes, il est très rapide. Le tamis occupe de l'espace O(N), mais cela n'a pas d'importance car le temps est très efficace. Regardons le code et ensuite nous passerons à l'explication du code -

var L = 10
var R = 5000
var arr = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,1);
arr[0] = 0
arr[1] = 0

for(var i = 2;i<=R;i++){
   if(arr[i] == 0){
      continue;
   }
   for(var j = 2; i*j <= R; j++){
      arr[i*j] = 0;
   }
}

var pre = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,0);
for(var i = 1; i<= R;i++){
   pre[i] = pre[i-1] + arr[i];
}
answer = pre[R]-pre[L-1]
console.log("The number of Prime Numbers in the given Range is: " + answer);

Dans le code ci-dessus, nous voyons l'implémentation du Tamis d'Eratosthène. Nous avons d'abord créé un tableau contenant la taille R, puis nous avons parcouru le tableau en utilisant la boucle for et pour chaque itération, si le nombre actuel n'est pas 1, cela signifie qu'il n'est pas premier, sinon il est premier et nous avons tous les nombres inférieurs à R qui sont les multiples du nombre premier actuel sont supprimés. Nous créons ensuite un tableau de préfixes qui stockera le nombre premier de 0 à l'index actuel et pourra fournir une réponse à chaque requête comprise entre 0 et R en temps constant.

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*log(log(N))), ce qui est bien meilleur que O(N*N) et O(N*(sqrt(N))). Par rapport au code précédent, le code ci-dessus a une complexité spatiale plus élevée de O(N).

Conclusion

Dans ce tutoriel, nous avons appris à trouver le nombre de nombres premiers dans une plage donnée à l'aide du langage de programmation JavaScript. Un nombre premier est un nombre qui possède exactement deux diviseurs parfaits. 1 n’est pas un nombre premier car il n’a qu’un seul diviseur parfait. Nous avons vu trois méthodes avec une complexité temporelle de O(N*N), O(N*sqrt(N)) et O(N*log(log(N))). De plus, la complexité spatiale des deux premières méthodes est O(1) et la complexité spatiale de la méthode Sieve of Eratosthène est O(N).

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!