Bonsoir ,
Je suis un peu débutant en programmation en C.
Mon prof de maths m'a donné l'idée de faire un programme avec lequel je puisse obtenir le PGCD (http://fr.wikipedia.org/wiki/PGCD pour les incultes ) de deux nombres.
Le principe, c'est d'utiliser l'algorithme d'Euclide (aussi appelé algorithme des divisions successives) qui consiste à obtenir le reste de la division Euclidienne de 2 entiers, puis de diviser ce reste par le diviseur, etc... jusqu'à ce qu'on obtienne 0 comme reste.
Le PGCD est alors le dernier reste non-nul (1 si les nombres sont premiers entre eux)
J'ai donc commencé le code, mais je bloque lorsque je dois reprendre le diviseur pour diviser le reste.
J'pense que certains passages sont mal expliqués, donc demandez plus d'infos

"puis de diviser ce reste par le diviseur"

désolé mais quelqu'un qui se considère comme non inculte devrai savoir que c'est l'inverse, il faut diviser le précédent diviseur par le reste obtenu.

Pour ce qui concerne tes soucis d'implémentation, dis nous ce qui te pose problème.

infos basique :
//division entière en C
int a = 15, b = 6;
int c = a/b; // ici c vaut 2
// reste de la division euclidienne (modulo)
int r = a%b; // ici r vaut 3

Attention ! À mon souvenir, la version de l'algorithme d'Euclide sur Wikipedia est moisie de chez moisie.

J'ai pas spécialement envie de t'aider (surtout parce que je risque de te donner direct la réponse en fait ). Essaie déjà de calculer le pgcd de 1664 et 1742 à la main à coup de divisions euclidiennes successives.

j'ai pas lu les algos fournis par la wikipedia mais ce schéma est tout a fait correct : http://fr.wikipedia.org/wiki/Fichier:PGCD.png

et aussi, joli nombre choisi au hasard

Il est correct pour les hypothèses qu'il se donne, mais : que faire si a<b ? si a=0 ? si on a des nombres négatifs (ce qui peut être utile pour accélérer un poil l'algorithme) ? etc.

le diagramme spécifie clairement a et b entiers naturels non nuls et a > b

Le shéma de guyver2 est exactement ce que je cherche à faire
Mais moi, ce que je voudrait savoir c'est comment faire pour que a prenne la valeur de b et b celle de r ? en C hein

Pour ça, tu as deux méthodes. Tu veux la méthode standard, ou celle du panda des montagnes de Chine ?

Je pense que la standarde suffira

Alors utilise une variable temporaire qui sert de tampon :

int t;

[…]

t = a;
a = b;
b = t;

[…]

Hum, je suis en train de me dire que c'est encore plus facile qu'échanger les valuers de a et b ce que tu veux faire en fait. Enfin bon, je te laisse le soin d'adapter ce que je viens de poster, ça ne te fera pas de mal de réfléchir un peu.

Arf, j'y arrive pas, et c'est pas faute d'avoir essayé
Voici mon code:

int main()
{
int a=1375;
int b=644;
int r;
do
{
r= a%b;
if (r=0)
{
printf("PGCD = %d", b);
}
else
{
a=b;
b=r;
}
}
while (r != 0);
return 0;
}

Je ne sait pas vraiment comment faire pour la vérification du reste s'il est égal à 0

« if (r=0) » Hahahaha

(désolé, c'est nerveux. )

En tout cas, cette ligne là ne teste pas si r est nul, et tu vas toujours partir dans la branche else du if (et le while est toujours faux).
Si tu veux mon avis, tu ferais mieux de faire l'affichage après la boucle do-while. C'est bien plus facile.

Oui, quelle erreur pas besoin de dire désolé, j'en ris moi-même
C'est donc if (r==0)

Et une fois cette ligne changée, ça marche
Mais je comprend pas trop ce que tu veux dire dans tes 2 dernières phrases

Je veux dire que ça c'est plus simple :

int main()
{
int a=1375;
int b=644;
int r;
do
{
r= a%b;
a=b;
b=r;
} while (r != 0);
printf("PGCD = %d\n", b);
return 0;
}