21xrx.com
2024-11-25 03:19:50 Monday
登录
文章检索 我的文章 写文章
Java实现辗转相除法求最大公约数和最小公倍数
2023-06-18 20:55:53 深夜i     --     --
Java 辗转相除法 最大公约数 最小公倍数

辗转相除法,又称欧几里得算法,是一种求最大公约数(GCD)的算法,它基于一个定理:两个整数的最大公约数,等于其中较小的数和两数的差的最大公约数。通过不断取两数的余数、然后将两数中较小的那个作为被除数,余数作为除数,以此类推,直到余数为0,此时的被除数即为最大公约数。

最小公倍数(LCM)则可以通过最大公约数和原始两数的乘积来计算。因为两数的乘积等于它们的最大公约数与最小公倍数的积,即LCM(a,b) * GCD(a,b) = a * b。

下面是Java代码实现辗转相除法求最大公约数和最小公倍数:


public class GCD {

  public static int getGCD(int a, int b) {

    if (b == 0)

      return a;

     else {

      return getGCD(b, a % b);

    }

  }

  public static int getLCM(int a, int b) {

    return (a * b) / getGCD(a, b);

  }

  public static void main(String[] args) {

    int a = 48;

    int b = 18;

    

    int gcd = getGCD(a, b);

    int lcm = getLCM(a, b);

    

    System.out.println("最大公约数:" + gcd);

    System.out.println("最小公倍数:" + lcm);

  }

}

在这个例子中,我们定义了一个GCD类,其中包含了两个静态方法getGCD和getLCM。getGCD方法用递归算法来计算最大公约数,getLCM方法则直接用最大公约数和原始两数乘积来计算最小公倍数。最后在main函数中,我们定义了两个整数a和b,并使用getGCD和getLCM方法来求出它们的最大公约数和最小公倍数。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复