教育改变生活

标题: Java求最大公约数和最小公倍数 [打印本页]

作者: 一秉 时间: 2020-5-18 16:29
标题: Java求最大公约数和最小公倍数
求最大公约数方法：辗转相除法
始终用较大数除以较小数，然后用余数代替较大数

整除时的除数就是最大公约数

举例：222 407求最大公约数
222 407(407除以222余数185)
222 185(222除以185余数37)
222 37 (222除以37余数0)
所以最大公约数为37
求最小公倍数方法：最小公倍数等于两数之积除以最大公约数
public class MultiplesAndConventions {
//求最小公倍数
static int minMultiples(int a,int b)
{
      return (a*b)/maxConventions(a,b);
}
//求最大公约数函数
static int maxConventions(int a,int b)
{
      int max = 0;
      if(a<b)
      { //交换a、b的值
         a=a+b;
         b=a-b;
         a=a-b;
      }
      if(a%b==0)
      {
         max = b;
      }
      while(a % b>0)
      {
         a=a%b;
         if(a<b)
         {
            a=a+b;
            b=a-b;
            a=a-b;
         }
         if(a%b==0)
         {
            max = b;
         }
      }
      return max;
}
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)