最大公因数，又称最大公约数和最大公约数，是指两个或两个以上整数的最大公约数。本文将介绍三种求两个正整数的最大公约数的方法，有需要的可以参考。
目录
题目描述问题解析代码实现方法1:穷举法2:辗转除法3:多相减损法
题目描述
求任意两个正整数的最大公约数
问题分析
最大公因数，又称最大公约数和最大公约数，是指两个或两个以上整数的最大公约数。A，B的最大公约数记为(A，B)。同样，A，B，C的最大公约数记为(A，B，C)，多个整数的最大公约数有相同的标记。求最大公约数的方法有很多，如质因数分解法、短除法、倒除法、多相损法等。最大公约数对应的概念是最小公倍数，A和B的最小公倍数记为[a，b]。
3354百度百科
有很多方法可以找到最大公约数。本文我将用穷举法、逐次除法、多相损法三种方法求两个正整数的最大公因式(最大公因式)。
代码实现
方法一：穷举法
穷举法(枚举法)是最简单、最直观的方法。
具体步骤如下：首先求两个数的最小值min(最大公约数必须小于等于最小值min)，然后从最小值min开始遍历(循环结束条件为i 0)。如果一个数是两个整数的因子，使用break退出遍历(退出循环)。此时遍历值I就是两个正整数的最大公约数。
#包含stdio.h
/**
* @brief求两个正整数的最大公因数(穷举法)
* @param num1第一个正整数
* @param num2秒正整数
* @返回最大公因数
*/
int Get _ Max _ Comm _ Divisor(int num 1，int num2)
{
int I=0；
//获取两个整数的最小值
int min=num1 num2？num 1:num 2；
//以降序从两个数字中的最小值开始遍历。
for(I=min；I 0；我-)
{
//i是num1和num2的公倍数。
if(num1 % i==0 num2 % i==0)
打破；
}
返回I；
}
int main()
{
int num1=0，num 2=0；
Puts('请输入两个正整数。');
scanf('%d%d '，num1，num 2)；
Printf('最大公约数为% d. \ n '，get _ max _ comm _ divider (num1，num 2))；
返回0；
}
运行结果
方法二：辗转相除法
相除，又称欧几里德算法，是指用来计算两个非负整数A，b的最大公约数，应用领域包括数学和计算机。公式gcd(a，b)=gcd(b，a mod b)。
欧几里德算法用于求两个正整数的最大公约数。古希腊数学家欧几里德在他的著作《The Elements》中首次描述了这种算法，因此将其命名为欧几里德算法。
扩展欧几里德算法可用于RSA加密等领域。
示例：
如果需要两个正整数1997和615的最大公约数，则使用欧几里德算法，具体如下：
1997/615=3(剩余152人)
65/152=4(剩余7)
12/7=21(剩余5)
7/5=1(剩余2)
5/2=2(剩余1)
2/1=2(剩余0)
到目前为止，最大公约数是1。
用除数和余数重复除法运算。余数为0时，取当前公式的除数为最大公约数，则1997和615的最大公约数为1。
3354百度百科
我觉得这个小算法特别神奇，但是不想深入研究(为什么翻来覆去的除法能找到最大公因式？).如果你想证明的话，你可以简单的自己证明，那我就选择背下来好了，呵呵。
虽然算法不太好理解，但是实现过程并不难。根据分而治之的概念，可以转化为代码。
具体步骤：首先求两个数num1和num2的余数余数。然后将num2赋给num1，设上一个余数的除数num2为下一个余数的被除数。同时将当前余数余数作为下一个余数的除数。这样做直到余数为0，此时除数num2是我们需要的最大公因数。
一开始两个数不需要大小不同，因为如果num1小于num2，那么余数结果还是num1，这样下次余数就变成num2% num1，也就是左边大的值作为被除数)。
#包含stdio.h
/**
* @brief求两个正整数的最大公因数(辗转除法)
* @param num1第一个正整数
* @param num2秒正整数
* @返回最大公因数
*/
int Get _ Max _ Comm _ Divisor(int num 1，int num2)
{
int remainder=num 1% num 2；//余数
而(余数！=0)
{
num1=num2//更新股息
num2=余数；//更新除数
余数=num 1% num 2；//更新余数
}
返回num2//最后的除数是最大公因数。
}
int main()
{
int num1=0，num 2=0；
Puts('请输入两个正整数。');
scanf('%d%d '，num1，num 2)；
Printf('最大公约数为% d. \ n '，get _ max _ comm _ divider (num1，num 2))；
返回0；
}
运行结果
方法三：更相减损法
055-79000是我国古代的数学专著，其中的“多相损”可以用来求两个数的最大公约数。原文是：
可以对半分，不可以对半分，设定分母，孩子的数量，才能以少减多，甚至更多的互相减损。让我们以相等的数量预约。
白话文翻译：
(如果需要近似分数，那么)如果能减半，就减半(就是用2近似分数)。如果不能减半，那就把分母和分子比较，把小数从大数中减去，互相相减，直到相减等于差，用这个相等的数来近似分数。
3354百度百科
还有一种方法叫折腾减法，好像和多相减法一样，至少原理是一样的。
减法(求最大公约数)，即尼各马科斯法，其特点是通过一系列减法来求最大公约数。比如：两个自然数，35和14，从大数中减去小数，(35，14)-(21，14)-(7，14)。此时7小于14。你要把14换成被减数，也就是(14，7)-(7，7)，再相减。
3354百度百科
我对刚才的分裂感到惊讶。没想到是减法。不过还是老规矩，只是用代码实现这个方法而不是证明。
与逆序除法不同，多相损法需要考虑两个数的大小。只有大的数可以作为被减数，小的数可以作为被减数。
实现步骤：先求两个正整数num1和num2的差diff，然后将num2赋给num1，让上一次减法中num2的减法为下一次减法的被减数。同时将当前差diff作为下一次减法的减数。这样做直到差值为0，此时除数num2是我们需要的最大公因数。
#包含stdio.h
/**
* @brief求两个正整数的最大公因数(多相损法)
* @param num1第一个正整数
* @param num2秒正整数
* @返回最大公因数
*/
int Get _ Max _ Comm _ Divisor(int num 1，int num2)
{
//两个数相减的结果(取正值)
int diff=num1 num2？num 1-num 2:num 2-num 1；
while(diff！=0)
{
num1=num2//更新被减数
num2=diff//更新减数分裂
diff=num1 num2？num1 - num2\
:num 2-num 1；//更新两个数相减的结果(取正值)
}
返回num2//最后还原是最大公因数。
}
int main()
{
int num1=0，num 2=0；
Puts('请输入两个正整数。');
scanf('%d%d '，num1，num 2)；
Printf('最大公约数为% d. \ n '，get _ max _ comm _ divider (num1，num 2))；
返回0；
}
运行结果
至于哪种方法效率更高，有兴趣的朋友可以计算一下。我只知道穷举是效率最低的。
以上是C语言中求最大公约数的三种方法的细节。更多关于C语言求最大公约数的信息，请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。