Comment vérifier efficacement les nombres premiers en JavaScript ?

Comment déterminer les nombres premiers en JavaScript

En JavaScript, l'identification des nombres premiers est une tâche de programmation courante. Un nombre premier est un entier positif supérieur à 1 qui n'est divisible par aucun autre entier positif sauf 1 et lui-même.

Solution 1 : Approche naïve

Le code fourni L'extrait offre un moyen simple de vérifier si un nombre est premier :

<code class="js">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true;

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 : Approche efficace

Une approche améliorée pour vérifier les nombres premiers est :

<code class="js">const isPrime = num => {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++) {
    if (num % i === 0) return false;
  }
  return num > 1;
};</code>

Ce code profite du fait que si un nombre n’est pas premier, son facteur est inférieur ou égal à sa racine carrée. En vérifiant les facteurs jusqu'à la racine carrée, nous pouvons éliminer efficacement les facteurs potentiels.

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!