C语言求最大公约数与最小公倍数 |21xrx.com

2023-06-19 13:42:54 深夜i -- --

最大公约数最小公倍数辗转相减法

在做算法题时，经常需要求最大公约数与最小公倍数。C语言提供了一些方法可以很方便地实现这两个操作。

1、求最大公约数

最大公约数是两个数共有的约数中最大的一个。求最大公约数的方法有很多种，这里介绍一种辗转相减法。具体步骤如下：

（1）如果a==b，则a或b即为最大公约数；

（2）如果a>b，则a=a-b，否则b=b-a；

（3）重复执行步骤（1）和（2）直到a==b；

（4）返回a或b即为最大公约数。

2、求最小公倍数

最小公倍数是两个数的公共倍数中最小的一个。求最小公倍数的方法有很多种，这里介绍一种基于最大公约数的方法。具体步骤如下：

（1）求出a和b的最大公约数；

（2）用a*b除以它们的最大公约数即为它们的最小公倍数。

通过以上方法，我们可以很方便地在C语言中实现求最大公约数与最小公倍数的操作，具体代码如下：

#include

int gcd(int a, int b)

{

return b==0 ? a : gcd(b, a%b);

}

int lcm(int a, int b)

{

return a*b/gcd(a,b);

}

int main()

{

int a,b;

printf("请输入两个整数：");

scanf("%d %d",&a,&b);

printf("最大公约数为：%d\n",gcd(a,b));

printf("最小公倍数为：%d\n",lcm(a,b));

return 0;

}

上一篇: idea打包java可执行jar包

下一篇: C语言与C语言程序设计的区别

()

相似文章