前言：
如今兄弟们对“c语言最大公约数和最小公倍数辗转相除法”大概比较着重，看官们都想要学习一些“c语言最大公约数和最小公倍数辗转相除法”的相关知识。那么小编在网上收集了一些关于“c语言最大公约数和最小公倍数辗转相除法””的相关文章，希望同学们能喜欢，小伙伴们一起来了解一下吧！求两个数的最大公约数和最小公倍数是非常经典的题型。无论是等级考试还是竞赛题中都会出现。此类题目同时多次出现在蓝桥杯、NOC的比赛中以及电子学会、NCT的Python考级原题中，它们的区别仅仅在于是否对算法复杂度有要求，题目还是这个样子。这里就不列举原题了，我们直接来看看如何解决这类问题吧。
一、最大公约数
输入两个正整数m和n，计算出这两个数的最大公约数并输出。
输入：
一行输入两个正整数，以空格隔开
输出：
两个数的最大公约数
输入样例：
12 18
输出样例：
6
这个问题有多种解决方法，最直观的方法我们首先想到的是枚举法。枚举法顾名思义从指定的范围内一个个找到我们需要的答案，找到答案后退出循环。
从数学的知识我们可以知道，我们首先要知道两个数中谁大谁小。最大公约数最大值为较小的数（如3和6的最大公约数），最小值为1（如3和5的最大公约数）。因此我们循环时需要从最大可能性依次减小，一直循环到1。枚举法的代码也很容易得到：
m, n = map(int, input().split())a = min(m, n) # 求出m和n中的最小值for i in range(a, 0, -1): if m % i == 0 and n % i == 0: print(i) break
这种方法虽然思路简单，但是并不是最优解。如果输入的数值较小看不出什么问题，假设输入两个十位数的质数，求它们的最大公约数，循环的次数就非常可怕了。因此，如果对算法复杂度有要求，我们就要对算法进行改进了。
我们可以借助于数学上求最大公约数的方法改进我们的算法。在数学上求最大公约数有三个方法：
找查约数法更相减损法碾转相除法
第一种方法就是枚举法，第二种和第三种方法如果改造成算法就可以极大减少算法复杂度了。
更相减损法的原理是将两个数的大数减去小数，得到的差再与小数比较，直到差与较小的数相等，则得到的差就是最大公约数。
m, n = map(int, input().split())while m != n: if m > n: m = m - n else: n = n - mprint(m)
碾转相除法的原理是以小的数除大数，所得的是整数，那这个数就是最大公约数，不然就用余数来除刚才的除数，直到得到整数，这时作为除数的就是最大公约数。
m, n = map(int, input().split())a, b = max(m, n), min(m, n)c = a % bwhile c != 0: a = b b = c c = a % bprint(b)二、最小公倍数
输入两个正整数m和n，计算出这两个数的最小公倍数并输出。
输入：
一行输入两个正整数，以空格隔开
输出：
两个数的最小公倍数
输入样例：
12 18
输出样例：
36
最小公倍数的问题我们依然可以使用枚举法解决，虽然枚举法不是最佳的答案，但是肯定能解决问题。那么我们要看一下最小公倍数的枚举范围。既然是公倍数，那必然大于等于较大的数，最小的可能就是较大的数（如5和10的最小公倍数），最大的可能是两个数的乘积（如11和13的最小公倍数）。因此我们从最小的可能开始循环，一直循环到两个数的乘积，如果这个数能被这两个数整除，则退出循环。枚举法的代码可以很容易得到：
m, n = map(int, input().split())a = max(m, n)for i in range(a, m * n + 1): if i % m == 0 and i % n == 0: print(i) break
同样，在对算法复杂度有要求的情况下，使用枚举算法计算两个大数的最小公倍数效率会显得非常低下。我们看看怎样优化，优化的过程还需要使用到数学的知识：最小公倍数=两个数的乘积÷最大公约数。
前面我们讲到了计算最大公约数的时候可以使用更相减损法和辗转相除法。我们借助最大公约数可以很容易得到最小公倍数。下面以借用碾转相除法求最小公倍数的代码（更相减损法思路一样，可以自己书写）：
m, n = map(int, input().split())a, b = max(m, n), min(m, n)c = a % bwhile c != 0: a = b b = c c = a % bd = m * n // bprint(d)
