最大公约数和最小公倍数 |
您所在的位置：网站首页 › 求最大公约数和最小公倍数的方法 › 最大公约数和最小公倍数 |
最大公约数和最小公倍数
|
一、问题描述
从键盘输入两个正整数a和b，求其最大公约数和最小公倍数。 二、算法思想及代码求最小公倍数算法：最小公倍数=两整数的乘积÷最大公约数 求最大公约数算法： （1）辗转相除法用较大的数除以较小的数，再用除数除以出现的余数（第一余数），接着，再用第一余数除以出现的第二余数，如此反复，直到余数为0为止，最后的除数就是这两个数的最大公约数。有两整数a和b： ① a%b得余数c ② 若c=0，则b即为两数的最大公约数 ③ 若c≠0，则a=b，b=c，再回去执行① 例如求27和15的最大公约数过程为： 27÷15 余12，15÷12余3，12÷3余0，因此，3即为最大公约数。 #include int main(){ int m,n,r,s; while(true){ printf("input 2 integers(m n): ") ; scanf("%d %d", &m, &n); if(m==0 || n==0) break; if(mb，则a=a-b② 若a12 )， 15－12＝3( 12>3 )，12－3＝9( 9>3 ) ，9－3＝6( 6>3 )，6－3＝3( 3==3 )，因此，3即为最大公约数。 #include int main(){ int m,n,s; while(true){ printf("input 2 integers(m n): ") ; scanf("%d %d", &m, &n); if(m==0 || n==0) break; s=m*n;//保留乘积用于求最小公倍数 while(m!=n){ if(m>n) m=m-n; else n=n-m; } printf("最大公约数：%d\n", n);//最大公约数 printf("最小公倍数：%d\n\n", s/n);//最小公倍数 } return 0; }
有两整数a和b： ① i=1 ② 若a，b能同时被i整除，则t＝i ③ i++ ④ 若 i a(或b)，则t即为最大公约数，结束 改进： ① i= a(或b) ② 若a，b能同时被i整除，则i即为最大公约数，结束 ③ i--，再回去执行② #include #include #define N 100 int gcd(int m, int n){ int i, k; for(i=2; i = 2; i--) { if(m%i==0 && n%i==0){ return i; } } return 1; } int lcm(int m, int n){ int t = gcd(m,n); return m*n/t; } int main(){ int m,n,s,t; while(true){ printf("input 2 integers(m n): "); scanf("%d %d", &m, &n); if(m==0 && n==0) break; printf("最大公约数：%d\n",gcd(m,n));//求最大公约数 printf("最小公倍数：%d\n\n",lcm(m,n));//求最小公倍数 } return 0; }
|
【本文地址】
今日新闻 |
推荐新闻 |