C语言求最大公约数的方法，辗转相除法，质因数分解法、短除法、更相减损法。

首先说一下什么叫最大公约数：

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。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