Comment juger les nombres premiers en javascript

Un nombre premier fait référence à un nombre qui n'a d'autre facteur que 1 et lui-même parmi les nombres naturels supérieurs ou égaux à 2. Les nombres premiers sont largement utilisés en cryptographie, en informatique et dans d'autres domaines, il est donc très utile d'implémenter un programme JavaScript capable de déterminer si l'entrée est un nombre premier.

En JavaScript, nous pouvons utiliser des boucles et des instructions conditionnelles pour déterminer des nombres premiers. L'idée de base est de juger le nombre saisi un par un. S'il existe des facteurs autres que 1 et lui-même, ce n'est pas un nombre premier, sinon c'est un nombre premier.

Ce qui suit est un programme javascript simple pour implémenter des nombres premiers :

function isPrime(num){
  if(num <= 1){   // 1不是素数
    return false;
  }
  for(var i = 2; i < num; i++){  // 从2到num-1逐个判断
    if(num % i == 0){  // 如果可以整除，说明不是素数
      return false;
    }
  }
  return true;  // 如果没有被整除，则是素数
}

Dans ce programme, nous déterminons d'abord si le nombre saisi est inférieur ou égal à 1. Si c'est le cas, ce n'est pas un nombre premier. Utilisez ensuite une boucle for pour déterminer si elle est divisible une à une à partir de 2. S'il est divisible, cela signifie que ce n'est pas un nombre premier et renvoie directement faux. S'il n'est pas divisible, cela signifie que c'est un nombre premier et renvoie vrai.

La complexité temporelle de ce programme est O(n), ce qui peut prendre beaucoup de temps pour juger de grands nombres, nous pouvons donc utiliser certains algorithmes d'optimisation pour améliorer l'efficacité.

L'un des algorithmes d'optimisation courants consiste à déterminer uniquement le nombre inférieur ou égal à la racine carrée du nombre saisi. Car lorsqu'un nombre n n'est pas un nombre premier, il doit être décomposé en deux facteurs a et b, et au moins un des facteurs est inférieur ou égal à sa racine carrée. Par conséquent, il nous suffit de déterminer si un nombre inférieur ou égal à la racine carrée du nombre saisi peut être divisible.

Voici le programme optimisé de jugement des nombres premiers JavaScript :

function isPrime(num){
  if(num <= 1){
    return false;
  }
  for(var i = 2; i <= Math.sqrt(num); i++){  // 只判断小于等于平方根的数
    if(num % i == 0){
      return false;
    }
  }
  return true;
}

La complexité temporelle de ce programme est O(√n), ce qui est beaucoup plus efficace que le programme précédent.

Dans les applications pratiques, des algorithmes plus avancés peuvent également être utilisés pour déterminer les nombres premiers, tels que la méthode du tamis d'Eratosthène et la méthode du tamis d'Euler. Ces algorithmes peuvent être utilisés pour calculer des nombres premiers dans une plage, et leur complexité temporelle se situe généralement au niveau linéaire ou logarithmique linéaire, ce qui les rend très adaptés aux calculs de nombres premiers à grande échelle.

En bref, utiliser javascript pour mettre en œuvre le jugement des nombres premiers peut nous aider à mieux comprendre les concepts et les applications des nombres premiers et peut améliorer notre niveau de programmation.

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!