Problème à comprendre code source C

Résolu/Fermé

greg - Modifié par Twinuts le 16/04/2014 à 11:07
greg - 20 avril 2014 à 00:27

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\n");
  printf ("3\n");
  guess = 5;
  while ( guess <= limit ) {
    factor = 3;
    while ( factor * factor < guess && guess % factor != 0 )
      factor += 2;
    if ( guess % factor != 0 )
      printf ("%d\n", 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.

A voir également:

Problème à comprendre code source C
Code asci - Guide
Code puk bloqué - Guide
Code telephone oublié - Guide
Code blocks free - Télécharger - Langages
Code windows 10 - Guide

3 réponses

Réponse 1 / 3

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
16 avril 2014 à 10:05

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\n", 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,

greg
17 avril 2014 à 20:10

Désolé, toujours pas compris cette histoire de factor*factor

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
17 avril 2014 à 22:12

C'est de la logique. Pas vraiment facile à expliquer.
J'essaie :

Pour déterminer si N est premier, on va tester successivement pour p.
Etape 1 : On teste déjà pour p entre 2 et racine(N). Dans ce cas, q sera entre racine(N) et N. Si N est premier, on ne trouvera pas p et q (p et q entiers) tel que N=p*q (p différent de 1 et de N).
Etape 2: On teste avec q>racine(N), on aura dans ce cas q entre 2 et racine(N). Le cas entre 2 et racine(N) a été testé en étape 1 (N=p*q=q*p => symétrie).
Donc l'étape 2 est inutile...

Donc, il suffit juste de tester les diviseurs entre 0 et racine(N).
Autrement dit, il suffit de tester factor<=racine(N) => factor*factor<=N

greg
19 avril 2014 à 22:43

Je pense avoir saisi.
Si j'ai bien compris factor * factor < guess est équivalent à factor < sqrt(guess) ?
Je suppose que l'auteur a utilisé cette méthode pour éviter de faire appel à la fonction sqrt() et ainsi optimiser son code ?
Si c'est ça, c'est plutôt des lacunes en math qui me bloquent car je ne savais pas qu'on pouvait faire comme ça et 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.
Merci fiddy.

Réponse 2 / 3

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
19 avril 2014 à 22:48

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

greg
20 avril 2014 à 00:27

Oui c'est ce que je voulais dire, peux tu mettre le sujet en résolu pour moi, j'ai une IP dynamique donc j'ai perdu les droits. Encore merci :)

Réponse 3 / 3

Twinuts Messages postés 5375 Date d'inscription dimanche 4 mai 2003 Statut Modérateur Dernière intervention 14 juin 2023 2
16 avril 2014 à 11:08

Salut,

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

Discussions similaires

[référencement] Ne pas être référencé

Code de renvoi d'appel : Ooredo, Mobilis...

Acces à snapchat temporairement désactivé

Code Free Wifi Secure : comment en récupérer

Discussions similaires

Newsletters