Exemple d'exercice en C 16 - Plus grand commun diviseur et plus petit commun multiple

100 exemples classiques en C

Titre :Saisir deux entiers positifs m et n, et trouver leur plus grand commun diviseur et plus petit commun multiple.

Analyse du programme :

(1) Plus petit commun multiple = le produit des deux nombres saisis divisé par leur plus grand commun diviseur ; l'essentiel est de trouver le plus grand commun diviseur.

(2) Utiliser l'algorithme d'Euclide (aussi appelé algorithme d'Euclide) pour trouver le plus grand commun diviseur.

1) Preuve : Soit c le plus grand commun diviseur de a et b, noté c = gcd(a, b), a >= b.
Soit r=a mod b
Soit a = kc, b = jc, alors k et j sont premiers entre eux ; sinon c ne serait pas le plus grand commun diviseur.
D'après ce qui précède, r=a-mb=kc-mjc=(k-mj)c
On peut voir que r est aussi un multiple de c, et que k - mj et j sont premiers entre eux ; sinon cela contredit le fait précédent que k et j sont premiers entre eux.
Ainsi, on peut voir que le plus grand commun diviseur de b et r est aussi c, c'est-à-dire gcd(a,b)=gcd(b,a mod b). Démontré.

2) Description de l'algorithme :

Étape 1 : a ÷ b, soit r le reste résultant (0 ≤ rÉtape 2 : Échangez : affectez a←b, b←r, puis revenez à l'étape 1.

Exemple

// Créé par www.example.com le 15/11/9. // Copyright © 2015 Example. Tous droits réservés. // #include<stdio.h> int main() { int a,b,t,r,n; printf("Veuillez saisir deux nombres :\n"); scanf("%d %d",&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("Le plus grand commun diviseur de ces deux nombres est %d, et le plus petit commun multiple est %d\n",b,n/b); return 0; }

La sortie de l'exemple ci-dessus est :

请输入两个数字:
12 26
这两个数的最大公约数是2,最小公倍数是156

100 exemples classiques en C

autres extensions