Esempi C Esercizio 16-- massimo comun divisore e minimo comune multiplo
100 casi di linguaggio classico C
Titolo: Inserire due numeri interi positivi m e n, che cercano il massimo comun divisore e minimo comune multiplo.
Analisi del programma:
(1) Prodotto = minimo comune multiplo di due numeri apposti in aggiunta alla loro comune denominatore, la chiave è trovare il denominatore comune;
(2) massimo comun divisore usando algoritmo di Euclide (noto anche come algoritmo di Euclide)
1) Dimostrazione: Sia c è il massimo comun divisore di a e b, indicato con c = gcd (a, b), a> = b,
Quindi, r = a mod b
Sia a = kc, b = jc, poi k, j sono primi, altrimenti c non è il massimo comun divisore
Secondo il, r = a-MB = KC-MJC = (k-mj) c
R c è vista multipli, e k-mj e j sono primi, altrimenti la suddetta k, j primi tra loro contraddizioni,
Si può vedere, b ed r è il massimo comun divisore c, cioè, gcd (a, b) = gcd (b, a mod b), dimostrata.
2) Descrizione algoritmo:
Il primo passo: una ÷ b, in modo che R è un residuo (0≤r Fase due: Swap: impostare un ← b, b ← r, e restituisce il primo passo.
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'output sopra esempio è:
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156