带你理解求最大公因数的算法
前言:在数学学习与计算机编程中，我们经常需要计算两个数字的最大公约数。它既能简化分数计算，也是密码算法、数据运算里最 基础的常用在数学学习与计算机编程中，我们经常需要计算两个数字的最大公约数。它既能简化分数计算，也是密码算法、数据运算里最基础的常用工具。
从古至今，人们总结出两种最经典、流传最广的求解方法：更相减损术与辗转相除法。两种算法底层逻辑相通，都依靠数字公因数不变的数学规律缩小数值，但运算方式、速度效率截然不同。
本文用最简单直白的语言，不带复杂公式，一步步拆解两种算法的原理、过程与优劣对比，带你彻底看懂古人智慧与现代最优解法的区别。
<1>更相减损术
#include <stdio.h>
int main()
{
int m,n;
scanf("%d%d",&m,&n);
while(m!=n)
{
while(m>n){m=m-n;}
while(n>m){n=n-m;}
}
printf("%d\n",m);
return 0;
}
1.先引入一个知识,两个数的公因数不会,因为两者相减而改变,列如两个数m , n 他们的公约数是d , m-n的公约数也是d
2.上面代码意思就是,输入两个值,大数-小数的差值,赋予给大值 乍一看!有点看不懂!
举个例子:(24 9) --- (15 9) --- (6 9) --- (6 3) --- (3 3) : (12 4) --- (8 4) --- (4 4)
24 9 的最大公约数是3 12 4 的最大公约数是4
3.首先两个数相减,公约数d一直存在 (如12与4 有1,2,4) , 只是说把数的范围减小了 懂这意思吗? 找数更好找了
然而为什么m != n 其实就是确定(锁定)最大公约数,原理是,越大的公约数，数字越早重合，越早停止循环(减的过程公约数会出来)
4.为什么减的过程公约数会出来呢?比如12 4两个数, 12可以由3个4组成 , 4可以由1个4组成 ,那不就公约数不就出来了,应该可以理解
<2>辗转相除法
#include <stdio.h>
int main()
{
int m, n, t;
scanf("%d%d", &m, &n);
while(n != 0)
{
t = m % n;
m = n;
n = t;
}
printf("%d\n", m);
return 0;
}
1.为什么先引入更相减损术?这是因为更相减损术的原理和辗转相除法的原理是一样的公约数不变，只是减法 变 批量减法 , 速度更很快
2.取余 = 一次性多次减法
如(24 9) --- (9 6) --- (6 3) --- (3 3) {这里要注意m = n与n = t} 这跟上面本质没什么区别啦
m n m n m n m n
3.这里还有一个区别的话，就是结束条件不同，为什么余数为0就结束了?
其一 我们知道大数与小数，如果说大数能够被小的数整除，那小的数就是它们的最大公因数(这个方法的本质)
那(12 9)举例 , 12%9=3 ---->(9 3)然后可以整除了,最大公约数就出来了
其二 取余%的步骤包含两个作用a.缩小范围 b.确定整除,一旦能够确定整除，那么就可以得到最大公约数
总结
一.更相减损术（减法版）
核心思想：
两个数一起变小，公因数永远不会消失。
只要两数不相等，就一直用大数减小数。数字会越来越接近，直到两个数完全相同。最后相等的数，就是最大公约数。
缺点：数字差距很大时，减法次数太多，计算很慢。
二.辗转相除法（取余%版，最优）
核心思想：
取余就是一次性连续减法，一步顶很多次相减。
用大数对小数取余数，再不断替换数字重复运算。直到余数变成0，此时剩下的数就是最大公约数。
优点：步骤极少、速度最快，是目前数学和编程公认最好用的标准方法。
三.本质
两种算法本质一模一样：公因数全程不变，只会保留最大公共因数。
减法温和易懂，适合理解原理；取余高效快速，适合实际做题与代码使用。
