kmmkの雑種系日記

学習まとめです。

【Java】競技プログラミングで使う最大公約数と最小公倍数の実装

最大公約数 (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

参考

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

【ユークリッドの互除法】やり方&証明を解説!センター試験にも役立つ! | Studyplus(スタディプラス)

ユークリッドの互除法まとめ(証明・最大公約数・不定方程式) | 理系ラボ