Exemples C Exercice 16-- le plus grand diviseur commun et moins communs multiples
100 cas de la langue classique C
Titre: Entrez deux entiers positifs m et n, cherchant le plus grand commun diviseur et moins commun multiple.
Analyse du programme:
(1) Produit = commun multiple de deux nombres entrés en plus de leur dénominateur commun, la clé est de trouver le dénominateur commun;
(2) le plus grand diviseur commun en utilisant l'algorithme euclidien (également connu comme algorithme d'Euclide)
1) Preuve: Soit c est le plus grand commun diviseur de a et b, notée c = PGCD (a, b), a> = b,
Donc, r = a mod b
Soit a = kc, b = jc, alors k, j sont premiers, sinon c est pas le plus grand commun diviseur
Selon le, r = a-mb = kc-mjc = (k-mj) c
R c est vue multiples et k-mj et j sont premiers, sinon le k précité, j coprime contradiction,
On peut voir, b et r est le plus grand commun diviseur c, à savoir, pgcd (a, b) = pgcd (b, a mod b), a prouvé.
2) Description de l'algorithme:
La première étape: a ÷ b, de sorte que R représente un reste (0≤r Deuxième étape: Swap: définir un ← b, b ← r, et retourne la première étape.
Source Code:
// Created by www.w3big.com on 15/11/9. // Copyright © 2015年 本教程. All rights reserved. // #include<stdio.h> int main() { int a,b,t,r; printf("请输入两个数字:\n"); scanf("%d %d",&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; int n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("这两个数的最大公约数是%d,最小公倍数是%d\n",b,n/b); return 0; }
L'exemple ci-dessus sortie est:
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156