最大公約数 (Greatest common divisor)

例題) 12と18の最大公約数を求めなさい。

この方法は「ユークリッドの互除法」を使用しています。

class Main {
  public static void main(String[] args) {
    System.out.println(gcd(12, 18));
  }
  // 最大公約数
  public static int gcd(int a, int b) {
    if (a > b) {
      int tmp = a;
      a = b;
      b = tmp;
    }
    if (a == 0) { return b; }
    return gcd(b % a, a);
  }
}

<><><><><><><><><><><>

output : 6

ユークリッドの互除法とは

①最大公約数を求めたい2つの数のうち、大きい数を小さい数で割る。

②割って出てきたあまりで①の計算で割る数だった数を割られる数として割る。

③そのあまりで②の計算で割る数だった数を割られる数として割る。

④③の操作をあまりが出なくなるまで繰り返す。

⑤最後の計算の割る数が求める最大公約数である。

最大公約数の意味と求め方！センター試験で使える解法を紹介 | Studyplus（スタディプラス）

最小公倍数 (Least common multiple)

例題）2と3の最小公倍数を求めなさい。

最小公倍数に関しては、最大公約数を求めて、それを元に求める方が簡単に解ける。

2と3の最大公約数をgとすると、g * 2 * 3が2と3の最小公倍数ということになる。

ということで実装してみる.

class Main {
  public static void main(String[] args) {
    System.out.println(lcd(2, 3));
  }

  // 最小公倍数
  public static int lcd(int a, int b) {
    int g = gcd(a, b);
    return g * a * b;
  }

  // 最大公約数
  public static int gcd(int a, int b) {
    if (a > b) {
      int tmp = a;
      a = b;
      b = tmp;
    }
    if (a == 0) { return b; }
    return gcd(b % a, a);
  }
}

<><><><><><><><><><>

output : 6