題目：輸入兩個正整數m和n，求其最大公約數和最小公倍數，
程式分析：
（1）最小公倍數=輸入的兩個數之積除于它們的最大公約數，關鍵是求出最大公約數；
（2）求最大公約數用輾轉相除法（又名歐幾里德演算法）
1）證明：設c是a和b的最大公約數，記為c=gcd(a,b),a>=b,
令r=a mod b
設a=kc，b=jc，則k，j互素，否則c不是最大公約數
據上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍數，且k-mj與j互素，否則與前述k，j互素矛盾,
由此可知，b與r的最大公約數也是c，即gcd(a,b)=gcd(b,a mod b)，得證，
2）演算法描述：
第一步：a ÷ b，令r為所得余數（0≤r<b）；若 r="0，演算法結束；b" 即為答案，<br=""> 第二步：互換：置 a←b，b←r，并回傳第一步，</b）；若>
實體：
1 #include<stdio.h> 2 int main() 3 { 4 int a,b,t,r,n; 5 printf("請輸入兩個數字：\n"); 6 scanf("%d %d",&a,&b); 7 if(a<b) 8 {t=b;b=a;a=t;} 9 r=a%b; 10 n=a*b; 11 while(r!=0) 12 { 13 a=b; 14 b=r; 15 r=a%b; 16 } 17 printf("這兩個數的最大公約數是%d，最小公倍數是%d\n",b,n/b); 18 19 return 0; 20 }
以上實體輸出結果為：
請輸入兩個數字： 12 26 這兩個數的最大公約數是2，最小公倍數是156
感謝你的閱讀，請用心感悟！希望可以幫到愛學習的你！！分享也是一種快樂！！！請接力，，，
點擊查看原文，謝謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/24367.html
標籤：C
上一篇：C 實戰練習題目15
下一篇：C 實戰練習題目17