[C]最大公约数和最小公倍数
程序员文章站
2022-07-04 23:24:15
求最大公约数也可以用递归实现 ......
/*
求最大公约数和最小公倍数 编写程序,在主函数中输入两个正整数 a,b,调用两个函数 fun1() 和 fun2(),分别求 a 和 b 的最大公约数和最小公倍数,在主函数中输出结果。 */ #include <stdio.h> int fun1(int a,int b); int fun2(int a,int b); int main() { int a = 0, b = 0, gcd = 0, lcm=0; scanf("%d,%d", &a, &b); gcd = fun1(a, b); lcm = fun2(a, b); printf("最大公约数:%d\n", gcd); printf("最小公倍数:%d\n", lcm); system("pause"); return 0; } //最大公约数 = 小数 与 (大数%小数) 的最大公约数
//若a<b,经过一次辗转相除后,a,b的值会互换,所以不需要考虑a,b谁大
int fun1(int a,int b) { int gcd = 0,r = 0;while (b != 0)//辗转相除法 { r = a % b; a = b; b = r; } gcd = a; return gcd; } //最小公倍数 = 两数相乘 / 最大公约数 int fun2(int a,int b) { int lcm = 0,gcd=0; gcd = fun1(a, b); lcm = a * b / gcd; return lcm; }
求最大公约数也可以用递归实现
int f( int m, int n) { if(m%n==0) return n; else return f(n, m%n); }
上一篇: 数组、字符串去重
下一篇: 深入理解设计模式(21):组合模式