isPrime en JavaScript

1. Solution naïve pour vérifier si un nombre est premier en JavaScript
2. Solution racine carrée pour vérifier si un nombre est premier en JavaScript

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).