Problème à comprendre code source C
Résolu
greg
-
greg -
greg -
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.
==========
==========
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.
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 ascii - Guide
- Comment déverrouiller un téléphone quand on a oublié le code - Guide
- Code puk bloqué - Guide
- Code activation windows 10 - Guide
- Code blocks - Télécharger - Langages
3 réponses
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,
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,
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 ;-)
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 ;-)
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
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.