首先说一下什么叫最大公约数：
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
1：辗转相除法：
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
这个方法我是在大二 《信息安全》 这门课学到的，主要是用这个算法进行加密：
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
在这里只说这个大概，如果想了解更多可以找这方面的书籍或者百度百科学一学。
在 《C语音设计试题汇编》 第五章填空5.58 有这么一个算法：
下面更正一下，我是打在57题里了，哈哈哈哈。好尴尬。没看到的自行略过即可。
这就是“辗转相除法”
以下为代码：
我要评论#include <stdio.h>
int main ()
{
int r, m, n;
printf("Please put in two counts m and n :\n");
scanf("%d%d",&m,&n);
if(m < n)
{
r = m;
m = n;
n = r;
}
r = m % n;
while(r)
{
m = n;
n = r;
r = m % n;
}
printf( "%d\n",n );
return 0;
}
另外如果想用调用的话：
可以这么写：
用for实现上面的函数
int fjzys(int k)
{
int i=2;
for ( ; i<=k ; i++ ) //当因数i<=k时，实现该循环，每次循环因数i自加1
for ( ; k%i==0 ; j++ ) //当k整除当前因数，实现该循环，每次循环下标j自加1
{
k/=i; //使k=k/i
a[j]=i; //存入因数
}
return 0;
}
解决上面的无法输出多个相同的质因数函数，无法输出，多个相同的质因数，如90=233*5，只能输出一个3.
如果不了解自己可以上机试一试。
2：质因数分解法：
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=235分解质因数只针对合数。
定义：
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。
分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似，还可以用来求多个数的公因式。
C语音算法：
3：短除法：
短除法是求最大公因数的一种方法，也可用来求最小公倍数。求几个数最大公因数的方法，开始时用观察比较的方法，即：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。后来，使用分解质因数法来分别分解两个数的因数，再进行运算。之后又演变为短除法。短除法运算方法是先用一个除数除以能被它除尽的一个质数，以此类推，除到商是质数为止
这个算法我还没了解透，所以不予证明，很抱歉。
4：更相减损法：
1：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
2：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。
前几天看到一个例子感觉对理解这个很有帮助：
1、用更相减损术求98与63的最大公约数。
解：由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公约数等于7。
2、用更相减损术求260和104的最大公约数。
解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即1322=52。
总结：我了解的也不是很深入，以后还得多多努力，也希望能帮到你们。
本文地址：https://blog.csdn.net/qq_41348629/article/details/107436157
如对本文有疑问， 点击进行留言回复！！
Codeforces Round #657 (Div. 2) C题
![[扩展欧拉函数] POJ2142The Balance](http://www.lhsxpumps.com/_images5/10qianwan/20200723/s_0_202007231557018103.png)
hdu2222 Keywords Search（ac自动机模板-kuangbin）
IOS开发控件视图day08:监听文本框状态设置按钮状态不可点击且变灰
网友评论