Code666 (代码贴、代码片段)

[C] C语言 输入两个正整数m和n，求其最大公约数和最小公倍数 →→→→→进入此内容的聊天室

来自 Ample Agouti, 2024-03-21, 写在 C, 查看 80 次.
URL http://www.code666.cn/view/8e63016e
  1. 题目：输入两个正整数m和n，求其最大公约数和最小公倍数。
  2.  
  3. 程序分析：
  4.  
  5. （1）最小公倍数=输入的两个数之积除于它们的最大公约数，关键是求出最大公约数；
  6.  
  7. （2）求最大公约数用辗转相除法（又名欧几里德算法）
  8.  
  9. 1）证明：设c是a和b的最大公约数，记为c=gcd(a,b),a>=b,
  10. 令r=a mod b
  11. 设a=kc，b=jc，则k，j互素，否则c不是最大公约数
  12. 据上，r=a-mb=kc-mjc=(k-mj)c
  13. 可知r也是c的倍数，且k-mj与j互素，否则与前述k，j互素矛盾,
  14. 由此可知，b与r的最大公约数也是c，即gcd(a,b)=gcd(b,a mod b)，得证。
  15.  
  16. 2）算法描述：
  17.  
  18. 第一步：a ÷ b，令r为所得余数（0≤r 第二步：互换：置 a←b，b←r，并返回第一步。
  19.  
  20.  
  21. #include<stdio.h>
  22. int main()
  23. {
  24.     int a,b,t,r,n;
  25.     printf("请输入两个数字：\n");
  26.     scanf("%d %d",&a,&b);
  27.     if(a<b)
  28.     {t=b;b=a;a=t;}
  29.     r=a%b;
  30.     n=a*b;
  31.     while(r!=0)
  32.     {
  33.         a=b;
  34.         b=r;
  35.         r=a%b;
  36.     }
  37.     printf("这两个数的最大公约数是%d，最小公倍数是%d\n",b,n/b);
  38.    
  39.     return 0;
  40. }

回复 "C语言 输入两个正整数m和n，求其最大公约数和最小公倍数"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666