定义
最大公因数:也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。
辗转相除法:欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
举例理解
比如现在要求这两个数 32,26的最大公约数,解法如下:
32/26=1...6 (此行除数26作下一行的被除数,余数作为除数)
26/6=4...2 (此行同理)
6/2=3...0 (此处余数为零,意味着最大公约数就是2)
反复把一个式子中的除数当作被除数去除余数,直到最后余数等于0。文章来源:https://www.toymoban.com/news/detail-566732.html
最大公约数就是最后那个式子的除数,本例就是2。文章来源地址https://www.toymoban.com/news/detail-566732.html
C语言代码
#include <stdio.h>
int main()
{
int u, v;
scanf("%d %d", &u, &v);
while (v != 0)
{
int tmp = u % v;
u = v;
v = tmp;
}
printf("%d", u);
return 0;
}
Visual Studio 2022运行
到了这里,关于辗转相除法——求最大公约数(易懂详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!