最大公因数算法

欧几里得算法

思路

比如说gcd(a,b)
那么假设 d 是 a,b 的公因数
那么d|a，d|b
那么 我们先假设 a=kb+x——————(1)
即用b表示a
那么 x =a%b
我们对式(1)变形
x=a-kb
两边对d取模
x%d=(a-kb)%d=0
那么也就是说d也是x的公因数
那么我们就可以求gcd(a,a%b)
一步一步便可将一个数变为0，另一个即为最大公因数

int BigestFactor(int m,int n)
{int r=m;while(r!=0){r=m%n;m=n;n=r;         }return m;
}

更相减损法

这个主要用于高精度，用高精度实现%运算比较麻烦
那么可以采用纯减法和除法的更相减损法
不贴代码了，也不叫简单，下面是大概步骤：
假如需要求 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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！