Comment déterminer efficacement si un nombre est premier en JavaScript ?

Vérification des nombres premiers en JavaScript

Cet article aborde le problème de déterminer si un nombre donné est premier ou n'utilise pas JavaScript. Un nombre premier est un entier supérieur à 1 qui n'est divisible par aucun autre nombre naturel sauf 1 et lui-même.

Solution 1

La méthode traditionnelle consiste à itérer à partir de 2 à la racine carrée du nombre saisi et en vérifiant si le nombre est divisible par l'un d'entre eux. Si c'est le cas, ce n'est pas premier ; sinon, c'est le cas.

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? (isPrime *= false) : (isPrime *= true);
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

Complexité temporelle : O(sqrt(n))
Complexité spatiale : O(1)

Solution 2

Une approche alternative utilise le fait qu'un nombre premier supérieur à 2 ne peut pas être impair. Ainsi, il suffit de vérifier la divisibilité par 2 puis par nombres impairs jusqu'à la racine carrée du nombre saisi. Cette optimisation réduit considérablement le temps d'exécution.

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

Complexité temporelle : O(sqrt(n))
Complexité spatiale : O(1)

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!