if(m < n){
int temp = 0;
temp = m;
m = n;
n = temp;
}
int r = m % n;
while(r!=0){
m = n;
n = r;
r = m % n;
}
return n;
这用的是碾转相除法,咱们中国的老祖宗几千年前就会的。
参考:http://baike.baidu.com/link?url=Tks9K7bY7klIEVQuOINVIEXDdM2Hu0Q8N_AxCaUp1Mz8XFUIskwJA2BFZn3ZaWIusdeTCAu7J5ADp5VQDwD2sLqA-SpKBYJkgXlv94J9E7YQ4zbG6kJ1_UFxwQifIQuqYvXhXmEndvVzkRt6BfIpnq
先对m n 的值判断 ,确保m>n 不然就交换值。
循环取余。余数为0 则跳出循环。得到公约数。如果不理解的话,需要补一下数学
首先,用 if语句来判断m是否大于n,如果小于,交换两者位置,因为辗转相除法要求m大于n.然后m对n取余,如果余数不等于0,就用原先的被除数当除数,余当被除数,继续取余,知道余为0结束。
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:
⒈ 若 r 是 a ÷ b 的余数,且r不为0, 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是:
⒈ 令r为a/b所得余数(0≤r<b)
若 r= 0,算法结束;b 即为答案。
⒉ 互换:置 a←b,b←r,并返回第一步。
这个算法简洁,请大神分析一下啊
public static int gcd(int m, int n) {
while (true) {
if ((m = m % n) == 0)
return n;
if ((n = n % m) == 0)
return m;
}
}