求最大公因数的三种算法及简要说明 |
您所在的位置:网站首页 › 57与38的最大公因数 › 求最大公因数的三种算法及简要说明 |
求最大公因数的三种算法及简要说明
1、连续整数法
从给定的最小的数开始按1递减,直至找到一个能被两者都整除的数。
public static int gcd1(int x, int y){
int min = Math.min(x,y);
while (x%min!=0|| y%min!=0){
min--;
}
return min;
}
2、辗转相除法
也叫欧几里得算法,两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数
证明: 假设正整数a>b,有a = kb + r(k,r皆为正整数,且r |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |