Problème à comprendre code source C Résolu/Fermé

Question

Bonjour, 
J'étudie un cours sur l'assembleur et dans les exemple, je suis tombé sur un code source permettant de trouver les nombres premiers jusqu'à une limite donnée par l'utilisateur. Le souci c'est que je ne comprend pas comment il fonctionne et pourtant en le compilant, je vois que ça marche comme prévu.

==========

#include <stdio.h>

int main (void)
{

unsigned guess;
  unsigned factor ;
  unsigned limit ;
  printf ("Rechercher les nombres premier jusqu'a : ");
  scanf("%u", &limit);
  printf ("2
");
  printf ("3
");
  guess = 5;
  while ( guess <= limit ) {
    factor = 3;
    while ( factor * factor < guess && guess % factor != 0 )
      factor += 2;
    if ( guess % factor != 0 )
      printf ("%d
", guess);
    guess += 2;
  }
  return 0;
}


==========

La partie qui me pose souci c'est la multiplication de factor par lui même, à quoi est ce que cela sert et surtout dès la première boucle, pour moi la condition n'est pas remplie et donc le reste à l'intérieur de la boucle ne devrait pas être executé.
Merci pour votre aide.

fiddy · Accepted Answer

Bonjour,

Je ridirige ton post dans la catégorie "C".

while ( factor * factor < guess && guess % factor != 0 )
factor += 2; 
Tant que factor n'est pas un multiple de guess, on continue de teste le suivant jusqu'à ce que factor < racine(guess) (ou factor*factor <guess). Pas besoin d'aller au delà. La boucle s'arrête donc pour deux raisons :
soit on a testé tous les diviseurs (factor)
soit le nombre n'est pas premier (il y a un factor qui divise guess).

if ( guess % factor != 0 )
printf ("%d
", guess); 
Si factor ne divise pas guess, c'est qu'on est sorti de la précédente boucle while pour l'autre raison. Autrement dit, le nombre guess est premier. Il faut donc l'afficher.

while ( guess <= limit ) {
Et on fait l'algorithme précédent pour tous les nombres jusqu'au nombre saisi par l'utilisateur (limit).

Sinon, l'algorithmique du code n'est pas parfaite. En effet, si l'utilisateur tape 2, le programme affichera 2 et 3 ;-). Il faudrait faire une condition d'affichage pour le 2 et le 3.

Cdlt,

Twinuts · Answer

Salut,

J'ai modifié ton poste pour ajouter les balies "code".

fiddy · Answer

Si j'ai bien compris factor * factor < guess est équivalent à factor < sqrt(guess) ? 
Exactement. Si a et b sont positif et si a < b alors sqrt(a) < sqrt(b).

Je suppose que l'auteur a utilisé cette méthode pour éviter de faire appel à la fonction sqrt() et ainsi optimiser son code ? 
Tout à fait.

je ne savais pas non plus qu'on pouvait valider qu'il s'agit, ou non, d'un premier en ne vérifiant que la racine du nombre. 
Objection ! On ne vérifie pas que la racine du nombre. On vérifie qu'il n'y a aucun diviseur inférieur à la racine du nombre.

Et oui, les mathématiques sont importantes en programmation ;-)

Problème à comprendre code source C

3 réponses

Discussions similaires