UC知道关于求最大公约数的程序
来源：百度知道 编辑：UC知道 时间：2024/06/01 18:27:43
int fun(int a,int b)
{
int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}
while((temp=a%b)!=0)
{
a=b;
b=temp;
}
return b;
}
这是网上找到的代码,请问下它的原理是什么?
{
int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}
while((temp=a%b)!=0)
{
a=b;
b=temp;
}
return b;
}
这是网上找到的代码,请问下它的原理是什么?
辗转相除吧
大数除小数的余数继续被除数除，直到余数为0
12，28
28 mod 12=4
12 mod4 =0
4就是最大公约数
详见http://baike.baidu.com/view/1376155.htm
最大公约数的定义：指某几个整数共有公约数中的最大一个。
例: 在2、4、6中，2就是2，4，6的最大公约数。
辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数, 则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤r＜b）
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步。
辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。