【ITニュース解説】🔢 GCD & LCM

システムエンジニアを目指す初心者がプログラミングを学ぶ上で、数学的な概念がどのように役立つかを理解することは非常に重要だ。その中でも、最大公約数（GCD: Greatest Common Divisor）と最小公倍数（LCM: Least Common Multiple）は、数字の中に隠されたパターンを解き明かし、プログラミングだけでなく、私たちの身の回りのさまざまな場面で非常に有用な考え方となる。この記事では、これらの基本的な概念が何であり、なぜ重要なのか、そしてどのようにプログラミングで活用できるのかを具体的に見ていこう。

まず、最大公約数と最小公倍数の定義から理解を深める。最大公約数、略してGCDとは、二つの整数をどちらも割り切ることのできる最大の数のことだ。例えば、12と18という二つの数がある場合、12を割り切れる数は1, 2, 3, 4, 6, 12であり、18を割り切れる数は1, 2, 3, 6, 9, 18である。この中で共通して割り切れる数、つまり公約数は1, 2, 3, 6となる。その中で最も大きい数が6なので、GCD(12, 18)は6となる。次に、最小公倍数、略してLCMとは、二つの整数のどちらの倍数にもなる最小の数のことだ。12の倍数は12, 24, 36, 48, ...と続き、18の倍数は18, 36, 54, ...と続く。この中で共通して現れる倍数、つまり公倍数は36, 72, ...となる。その中で最も小さい数が36なので、LCM(12, 18)は36となる。ここで重要な関係性として、二つの数aとbに対して、LCM(a, b)とGCD(a, b)を掛け合わせると、ちょうどaとbを掛け合わせた数になるという法則がある。つまり、LCM(a, b) × GCD(a, b) = a × b が常に成り立つ。この関係を知っていると、どちらか一方を効率的に求められれば、もう一方も簡単に計算できる。

では、なぜこれらの概念が重要で、どのような場面で使われるのだろうか。一つは「分数の簡約」だ。例えば、18/24という分数があった場合、分子と分母をそれぞれの最大公約数で割ることで、最も簡単な形にすることができる。18と24のGCDは6なので、18を6で割ると3、24を6で割ると4となり、分数は3/4となる。これは日常生活でもよく使う考え方だ。二つ目は「スケジューリング問題」だ。異なる周期で繰り返される事柄が、次にいつ同時に発生するかを調べたいときにLCMが役立つ。例えば、あるタスクが12日ごとに実行され、別のタスクが18日ごとに実行されるとする。これらのタスクが次に同時に実行されるのはいつかを知りたい場合、12と18のLCMを計算すると36日後ということがわかる。このように、繰り返しのパターンを見つける際にLCMは非常に強力なツールとなる。その他にも、数多くの数学的アルゴリズムやプログラミングの競技問題、計算の効率化など、多岐にわたる場面でGCDとLCMは基礎的な要素として活用される。

プログラミングでGCDを計算する最も効率的な方法の一つに、「ユークリッドの互除法」というアルゴリズムがある。これは非常に古くから知られている方法で、その考え方はとてもシンプルだ。二つの正の整数aとb（ただしa > bとする）の最大公約数は、bと「aをbで割った余り」の最大公約数に等しい、という性質を利用する。これを繰り返し適用することで、最終的に余りが0になったときの割る数が最大公約数となる。具体的な手順は次のようになる。まず、二つの数aとbがあり、bが0でなければ、aをbで割った余りを新たなbとし、元のbを新たなaとする。この操作をbが0になるまで繰り返すのだ。bが0になったとき、その時のaの値が最大公約数となる。例えば、GCD(18, 12)を計算する場合を考えてみよう。

最初の状態：a = 18, b = 12

1. bが0ではないので、処理を続ける。 一時的な変数tempにb（12）を保存する。 bを「a（18）をb（12）で割った余り」（18 % 12 = 6）にする。 aをtemp（12）にする。 新しい状態：a = 12, b = 6
2. bが0ではないので、処理を続ける。 一時的な変数tempにb（6）を保存する。 bを「a（12）をb（6）で割った余り」（12 % 6 = 0）にする。 aをtemp（6）にする。 新しい状態：a = 6, b = 0
3. bが0になったので、繰り返しを終了する。 現在のaの値である6が最大公約数となる。

このように、ユークリッドの互除法は少ない回数の計算でGCDを求めることができる。そして、LCMを計算する際には、先ほど触れた「LCM(a, b) × GCD(a, b) = a × b」の関係を利用するのが最も安全で効率的だ。具体的には、LCM(a, b) = (a × b) / GCD(a, b) という式で求められる。このとき、先にGCDを計算しておくことで、aとbを掛け合わせたときに発生する可能性のあるオーバーフロー（数値が大きくなりすぎてコンピュータで扱える範囲を超えること）のリスクを軽減できる場合がある。

これらの概念をJavaというプログラミング言語で実装してみよう。まずGCDの計算だ。public static int gcd(int a, int b)という関数（メソッドと呼ぶ）を作成する。public staticは、このメソッドがどこからでも呼び出せて、特定のオブジェクトに依存しないことを意味する。intは整数を扱い、aとbは入力される二つの整数だ。メソッドの中身はユークリッドの互除法をそのままコードに落とし込む。

Copy
1public static int gcd(int a, int b) {
2    while (b != 0) { // bが0でない限り繰り返す
3        int temp = b; // bの値を一時的に保存
4        b = a % b;    // aをbで割った余りを新しいbとする
5        a = temp;     // 保存していたbの値を新しいaとする
6    }
7    return a; // bが0になったときのaがGCD
8}

このコードは、先ほどのユークリッドの互除法の擬似コードと全く同じロジックで動く。while (b != 0)は「bが0ではない間、{}の中の処理を繰り返し実行する」という意味だ。%記号は「剰余演算子」といい、割り算の余りを計算する。tempという一時的な変数を使ってbの値を保持し、aとbの値を適切に更新していく。最終的にbが0になったとき、ループは終了し、その時点でのaの値が返される。

次に、LCMの計算メソッドは、GCDをすでに計算できる状態であれば非常にシンプルに実装できる。

Copy
1public static int lcm(int a, int b) {
2    return (a * b) / gcd(a, b); // aとbの積をGCDで割る
3}

このメソッドでは、gcd(a, b)を呼び出してGCDを取得し、その結果を使ってLCMを計算している。このように、一度実装した機能を再利用することで、コードはより簡潔になり、間違いも減らせる。

実際にこれらのメソッドが正しく動作するか確認するために、プログラムを実行するmainメソッド内でテストを行う。

Copy
1public static void main(String[] args) {
2    int num1 = 12;
3    int num2 = 18;
4    System.out.println("GCD: " + gcd(num1, num2)); // 出力は "GCD: 6"
5    System.out.println("LCM: " + lcm(num1, num2)); // 出力は "LCM: 36"
6}

このmainメソッドは、num1とnum2にそれぞれ12と18を代入し、先ほど定義したgcdメソッドとlcmメソッドを呼び出して結果を表示する。実行すると、期待通りGCDが6、LCMが36と表示されるはずだ。

これらの概念は、単にプログラミングの基礎知識としてだけでなく、現実世界の様々な問題を解決する上でも役立つ。例えば、先述の分数簡約のように、データの表示をよりシンプルにしたり、リソースの最適な配分を考えたりする場面でGCDが活用できる。また、工場の生産ラインで複数の機械のメンテナンス時期を合わせる、鉄道の運行ダイヤで異なる路線の接続を最適化するといった「タスクスケジューリング」の問題では、LCMが重要な役割を果たす。このように、GCDとLCMは、数学的な基礎でありながら、プログラマーが直面する具体的な課題を解決するための強力なツールとなるのだ。

まとめると、最大公約数（GCD）は二つの数を割り切る最大の数であり、最小公倍数（LCM）は二つの数の最小の共通の倍数である。GCDを効率的に求めるアルゴリズムとしてユークリッドの互除法があり、これはプログラミングにおいて非常に広く使われている。そして、LCMはGCDを利用することで安全かつ効率的に計算できる。これらの概念は、単なる数学の知識に留まらず、分数の簡約から複雑なスケジューリング問題、さらには競技プログラミングのような高度なアルゴリズムに至るまで、数多くの場面で基礎となる重要な考え方だ。システムエンジニアを目指す上では、こうした基本的な数学的ツールを理解し、プログラミングで応用できる能力が求められる。