0
votes

Additionner tous les nombres premiers jusqu'à un certain nombre

Je suis censé écrire un algorithme qui renvoie la somme de tous les nombres premiers jusqu'à un certain nombre (argument), y compris l'argument lui-même. Ce code semble fonctionner très bien (je l'ai testé sur des nombres plus petits), cependant il doit y avoir un bogue car lorsque je passe 977 comme argument, le programme renvoie 108789 , ce qui n'est pas censé être correct. Selon freecodecamp.org, il devrait renvoyer 73156 . J'ai déjà vérifié le tableau avant d'ajouter les valeurs mais je ne vois pas le problème ici.

function sumPrimes(num) {
  function isPrime(n){
   return ((n/2 === 1 || n/3 === 1 || n/5 === 1 || n/7 === 1)?true: 
     (n%2===0 || n%3 === 0 || n%5 ===0 || n%7 === 0)? 
     false:true);
  };

  let result = [];
  let final;

  for(let i = 2; i <= num; i++){
    if(isPrime(i)){
      result.push(i);
    }
  }

  final = result.reduce((x,y) => x + y);

  console.log(final); // returns 108789

}

sumPrimes(977);

javascript primes

1 commentaires

Vous feriez mieux de vérifier votre tableau final. il comprend 121 qui peut être divisé par 1, 11, 121.

5 Réponses :

2
votes

Votre isPrime est complètement faux. Tout d'abord, vous ne vérifiez la divisibilité que par les quatre premiers nombres premiers; vous devriez vérifier la divisibilité par tous les nombres premiers jusqu'à la racine carrée du nombre que vous testez pour être sûr. (Vous pouvez également tester avec des nombres non premiers si vous ne voulez pas vous soucier de trier les nombres premiers des non-nombres premiers à ce stade.) Deuxièmement, que le reste soit 1 ou non ne fait aucune différence - c'est seulement entre 0 et non 0 c'est important.

Les algorithmes de test de primalité sont très connus et décrits partout sur le Web; pour commencer, jetez un œil à Wikipedia sur nombres premiers pour un aperçu, et ici pour l'algorithme spécifique que je suppose que vous recherchiez, mais pour votre cas d'utilisation spécifique (somme de tous les nombres premiers inférieur à N), le Tamis d'Ératosthène devrait être bien meilleur.

1 commentaires

Merci, je n'avais pas réalisé cela, cette vérification de premier ordre a été une telle douleur dans le cul pour moi mais j'espère que je pourrai bientôt comprendre.

0
votes

Votre fonction isPrime () est incorrecte. Si vous voulez gérer autre chose que des nombres premiers trivialement petits, vous ne pouvez pas simplement coder en dur les nombres premiers à vérifier. Par exemple, isPrime (143) retournera vrai, mais 143 = 11 * 13 n'est donc pas premier.

0 commentaires

0
votes

Votre fonction principale ne fonctionne pas correctement, vous voudrez peut-être lire ce post sur la création d'un. Le reste de votre fonction, cependant, semble agir comme prévu.

0 commentaires

3
votes

Votre méthode isPrime () est incorrecte. Vous pouvez faire quelque chose comme ci-dessous à la place.

Edit: la complexité de l'algorithme est diminuée de O (n) à O (sqrt (n)) comme indiqué par @Amadan

function sumPrimes(num) {

      function isPrime(n){
           for(let i = 2, k = Math.sqrt(n); i <= k; i++)
              if(n % i === 0) 
                 return false; 
           return true;
      };

      let result = [];
      let final;

      for(let i = 2; i <= num; i++){
        if(isPrime(i)){
          result.push(i);
        }
      }

      final = result.reduce((x,y) => x + y); 
      console.log(final); // returns 73156
    }

4 commentaires

Un grand merci à vous, c'est simple et compréhensible.

Pourquoi feriez-vous une boucle de 0 à n , puis excluriez n et 1 ? (Laissant de côté l'étrangeté de n% 0 , qui, heureusement, vous permet de NaN en JavaScript plutôt que de casser votre code) Pourquoi ne pas simplement faire une boucle à partir de 2 à n - 1 ? Ou mieux encore, de 2 à Math.sqrt (n) , ce qui est mathématiquement suffisant (comme mentionné dans ma réponse)?

@Amadan est tout à fait d'accord ... je modifierai tout de suite. C'est bien mieux que ça.

ouais ... J'ai raté ça. Je ne pouvais même pas le voir. Merci encore.

0
votes

La méthode que vous utilisez est erronée car elle ne vérifie qu'un certain nombre de valeurs, ce qui serait problématique pour les grands nombres.

Comme mentionné dans l'une des réponses ci-dessus, parcourir tous les nombres jusqu'à la racine carrée de ce nombre est également une méthode valide, mais il existe une méthode encore plus rapide et plus efficace appelée Sieve of Eratosthenes.

Cette méthode fonctionne en supprimant les résultats que nous connaissons déjà comme faux et en ne les calculant pas.

Vous pouvez en savoir plus ici - Tamis d'Ératosthène

0 commentaires