求最大公因数

来源：百度知道 编辑：UC知道 时间：2024/05/22 20:24:03
898440451 ； 899160187
求最大公因数，一定要方法！！！！！！！ 硬算肯定是不行的。
basic13 的方法我知道，我就是觉得这个方法好像不适用于如何数，才提问的。他们的最大公约数是

29989

我用c#写的
int r,a=898440451,b=899160187;
while (b != 0 )
{r =a%b;
a = b;
b = r;
}
textBox1.Text=a.ToString();
就是用上面的辗转相除法
用递归函数是
int gcd(a, b) {
if a mod b<>0
return gcd(b, a mod b);
else
return a;
}
textBox1.Text=gcd(898440451,b=899160187).ToString();

用辗转相除法求最大公约数
m为大数字,n为小数字
m对n求余为a, 若a不等于0
则 m <- n, n <- a, 继续求余
否则 n 为最大公约数

899160187/898440451=1.XXXX 余719736
898440451/719936=1247.XXXX 余680259
719936/680259=1.XXXX 余39677
680259/39677=17.XXXX 余5750
39677/5750=6.XXXX 余5177
5750/5177=1.XXXX 余573
5177/573=9.XXXX 余20
573/20=28.65 余13
20/13=1.XXXX 余7
13/7 余6
7/6 余1
~
1就是其最大公约数

用短除自己慢慢算

方法是这样的：
假设898440451＝a×N，899160187＝b×N，其中a、b、N都是自然数，a、b互质
那么N就是它们的最大公因数
于是有：899160187－898440451＝719736＝(b-a)×N
也就是说它们的最大公因数N也是719736的一个因数
对719736进行初步分解：719