利用Java求最大公约数与最小公倍数的算法

时间:2022-12-22 00:30:41
//利用Java求最大公约数与最小公倍数的算法 
//求最大公约数

//利用循环,大的数除以小的数,若余数不为0,则让小的数作为被除数,余数作为除数,直到余数为0,此时较小的数为最大公倍数


int getGreatestCommonMeasure(int a,int b){ //求最大公约数
if(b == 0)
return 1;

if(a > b){
int temp = a;
a = b;
b = temp;
}

int k = b%a;

while(k != 0){
b = a;
a = k;
k = b%a;
}

return a;
}
//求最小公倍数

//最小公倍数就是两个数相乘再除以最大公约数


int getLeastCommonMultiple(int a,int b){ //求最小公倍数
return a*b/getGreatestCommonMeasure(a,b);

}