最大公约数与最小公倍数的求解是很多初学C的人所面临的一道问题。当然这道问题并不难解答，也有很多人已经写过相关的博客，我在此书写此篇博
问题：请从键盘上输入两个数值 x，y，请用C语言求出这两个数值的最大公约数与最小公倍数。
首先，我们要想解决这道问题，就要了解什么是最大公约数与最小公倍数。
最大公因数；也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。----来源百度百科
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。----来源百度百科
了解了其含义，接下来就是构思算法，通常而言c语言求最大公约数，求解最大公约数有三种算法，而最小公倍数的求解，我们可以很容易的推断出，最小公倍数等于两个数值的乘积除以这两个数值的最大公约数。那么接下来的算法我将在此一一进行列举和解释。
和我一样的初学者。
1.辗转相除法：
又名欧几里德算法（Euclidean algorithm），它是已知最古老的算法，其可追溯至公元前300年前。 ----来源百度百科
辗转：望文生义c语言求最大公约数，就是翻来覆去。相除就很好理解了，就是进行除法运算。
辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。
假设两数为 x，y。
先令 z = x % y ;
之后 y 赋给 x 即令 x = y ;
再将 z 赋给 y 即令 y = z；
辗转相减，其终止条件为：y 等于0时。
下面给出代码：
#include
int main()
{
int x, y, z, m, n;
printf("请输入两个数：");
scanf_s("%d%d", &x, &y);
m = x, n = y;
while (y != 0)
{
z = x%y;
x = y;
y = z;
}
printf("最大公约数是: %d\n", x);
printf("最小公倍数是: %d\n", m*n / x);
system("pause");
return 0;
}
2.辗转相减法：
即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。----来源百度百科
辗转相减法即通过对两数的不断减法运算。
假设两数为 x, y。
当 x > y 时，令 x = x - y;
反之，则令 y = y - x;
之后一直辗转相减，直至 x = y 时，终止。
下面给出代码：
#include
int fun(int a,int b)
{
if(ab)
return fun(a-b,b);
else
return a;
}
int main()
{
int a=28,b=14;
int c= fun(a,b);
printf("%d",c);
return 0;
}
评论列表