HOWTO · JavaScript
isPrime en JavaScript
Ce tutoriel enseigne comment vérifier si un nombre est premier en JavaScript.
Sur cette page
Un nombre premier est supérieur à un avec deux facteurs - un et lui-même. Cela signifie que les nombres premiers laissent toujours un reste lorsqu’ils sont divisés par d’autres nombres. Les autres nombres supérieurs à un avec plus de deux facteurs sont appelés nombres composés.
Cet article discutera de différentes méthodes pour vérifier si un nombre est premier en JavaScript.
Solution naïve pour vérifier si un nombre est premier en JavaScript
Le moyen le plus simple de vérifier si un nombre n est premier est d’itérer de 2 à n-1 puis de vérifier si n est divisible par chacun d’eux.
function isPrime(n) {
if (n <= 1) return false;
for (var i = 2; i <= n - 1; i++)
if (n % i == 0) return false;
return true;
}
console.log(isPrime(70));
console.log(isPrime(23));
Complexité temporelle
On itère n-2 fois de 2 à n-1. La complexité temporelle de cette solution est O(n).
Complexité spatiale
La complexité spatiale de cette solution est O(1).
Solution racine carrée pour vérifier si un nombre est premier en JavaScript
La solution ci-dessus peut s’améliorer en itérant uniquement jusqu’à sqrt(n). Il est basé sur le fait que sqrt(n) * sqrt(n) = n, et il doit y avoir au moins un facteur inférieur ou égal à sqrt(n). Si nous ne trouvons aucun facteur dans la plage de [2, sqrt(n)], cela signifie que le nombre n est un nombre premier.
function isPrime(n) {
if (n <= 1) return false;
for (var i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
console.log(isPrime(70));
console.log(isPrime(23));
Complexité temporelle
Puisque nous itérons les premiers facteurs potentiels sqrt(n), la complexité temporelle de la solution ci-dessus est sqrt(n).
Complexité spatiale
La complexité spatiale de cette solution est O(1).
