：辗转相除法求最大公约数(m和n)

输入两个正整数m和n，求它们的最大公约数和最小公倍数。

用滚动除法求最大公约数

算法说明：

如果a不等于0c语言公约数和公倍数，m到n的余数就是a

那么m，否则n是最大公约数

最小公倍数 = 两个数的乘积 / 最大公约数

#包括

int main()

{

int m, n;

int m_cup, n_cup, res; /*除数、除数、余数*/

printf(“请输入两个整数：n”);

scanf(“%d %d”, &m, &n);

如果 (m > 0 && n >0)

{

m_cup = m;

n_cup = n;

res = m_cup % n_cup;

while (res != 0)

{

m_cup = n_cup;

n_cup = res;

res = m_cup % n_cup;

}

printf(“最大公约数：%dn”, n_cup);

printf(“租赁公倍数：%dn”, m * n / n_cup);

}

else printf(“错误！n”);

返回 0;

}

★关于折腾的方法，我搜了一下，在中国古籍《九章算术》中有记载，摘录如下：

逼近技术说：“如果能分成两半，如果不能分成两半，设置分母和孩子的数量，这样可以减少孩子的数量，减少每个人的损失其他，求相等。p>

里面提到的“等数”就是最大公约数。求“等数”的方法是“更减”的方法，其实就是转转除法。

确定最大公约数是一种更好且更快的方法。

你能快速找到数字 52317 和 75569 的最大公约数吗？一般来说，你会寻找一个公共因素。这个问题很麻烦，很难找，而且素数很大。

现在我将教你如何通过滚动和除法找到最大公约数。

先将较大的75569除以52317，得到商1，余数为23252，再将52317除以23252，得到商2，余数为5813，然后用23252作为被除数，5813作为除数，就除以商Count 4。所以5813是75569和52317的最大公约数。如果你用因式分解的方法，你肯定找不到。

那么，为什么这种折腾除法得到最大公约数呢？下面就和大家聊聊。

例如，如果要求两个整数a和b的最大公约数，a>b，那么我们先将a除以b得到商8，余数r1：a÷b=q1 …r1 当然，我们也可以把上面的公式改写成乘法公式：a=bq1+r1——l)

如果r1=0，那么b是a和b的最大公约数3。如果r1≠0，继续除，b除以r1c语言公约数和公倍数，我们也可以得到和上面一样的公式：

b=r1q2＋r2——2）

如果余数 r2=0，那么 r1 是 3 的最大公约数。为什么？因为如果2）公式变成b=r1q2，那么b1r1的公约数必然是a1b的公约数。这是因为一个数可以同时整除b和r1，那么根据公式l)，它一定能整除a，所以它也是a1b的公约数。

反之，如果一个数d可以同时整除a1b，那么根据公式1），它一定也能整除r1，所以b1r1也有公约数。

这样，a和b的公约数与b和r1的公约数完全一样，那么这两对的最大公约数也必须相同。 b1r1的最大公约数，当r1=0时，不是r1吗？所以a和b的最大公约数也是r1。

有人会说，如果r2不等于0呢？这当然是在继续，将 r1 除以 r2，…直到余数为零。

在这种方法中，先做除数，然后被除数变成被除数。