辗转相除法（欧几里得算法）求最大公因数

我们在刚接触编程的时候，遇到求最大公因数的题，往往会选择从n-1开始用循环枚举的方法来找出能被它整除的最大的数，这种算法虽然操作简便易于理解，但时间复杂度是O(n)级别的遇到要求严格的题，可能会时间超限。
下面我们来介绍一种优秀的求最大公因数的方法——辗转相除法

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

下面用代码来实现一下
循环实现

#include <cstdio>
#include <algorithm>
using namespace std;
int main(){int a, b, r = 1;scanf("%d%d", &a, &b);if(a < b)               //如果aswap(a, b);         //则交换a,b的值while(r != 0){r = a % b;          //a除以b,将第一余数赋给ra = b;              //把除数赋给ab = r;              //把第一余数赋给b,下一次循环用除数除以第一余数,以此类推,直到出现的余数为0}printf("%d\n", a);      //此时的a为最后一次相除的除数,即a,b的最大公因数return 0;
}

递归实现

#include <stdio.h>
int gcd(int a, int b){return b == 0 ? a : gcd(b, a%b);
}
int main(){int a, b;scanf("%d%d", &a, &b);printf("%d\n", gcd(a,b));return 0;
}

求完了最大公因数，再让你求最小公倍数该怎么办呢？
我们是不是让其中一个数除以它们的最大公因数，再乘上另一个数是不是就可以了！
比如：6和9的最大公因数是3，让6除以他们的最大公因数3得2，再乘上9得18，18是不是就是6和9的最小公倍数呢！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！