c语言最大公约数的求法

回答

爱扬教育

2022-02-07

c语言最大公约数的有三种求法：
穷举法（枚举法）：
从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。
更相减损法：
Steps：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

扩展资料

　　以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

　　则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

　　辗转相除法（欧几里德法）：

　　C语言中用于计算两个正整数a,b的最大公约数，采用函数嵌套调用形式进行求两个数的最大公约数。其算法过程为：

　　前提：设两数为a,b设其中a做被除数,b做除数,temp为余数

　　Steps:大数放a中，小数放b中；

　　求a/b的余数；

　　若temp=0则b为最大公约数；

　　如果temp!=0则把b的值给a,temp的值给a；

　　返回第二步。