欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[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);
 }