Exemple d'exercice en C 16 - Plus grand commun diviseur et plus petit commun multiple
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
La sortie de l'exemple ci-dessus est :
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156autres extensions