C++でLCMが最大になるN以下の3つの整数を見つける方法

はじめに

このチュートリアルでは、最小公倍数(LCM)の概念を応用したプログラムを作成します。タイトルのとおり、与えられた数 N 以下の整数の中から3つの数を選び、その LCM が最大になる組み合わせを求めるのが目的です。

まずは例から見ていきましょう。本題に入る前に、LCM とは何かを確認し、2つの数の LCM を求めるプログラムを書いてみます。

LCM(最小公倍数)とは

LCM(Least Common Multiple:最小公倍数)とは、複数の数に共通する倍数のうち最も小さいものを指します。正の整数 a と b に対して、LCM は a でも b でも割り切れる最小の整数です。

また、2つの整数が互いに素(共通の約数を持たない)場合、LCM はそれらの積と等しくなります。たとえば 4 と 5 は互いに素なので、LCM は 4 × 5 = 20 となります。

2つの数のLCMを求めるプログラム

まず、任意の2つの正の整数の LCM を求める基本的なプログラムを書いてみましょう。

#include <iostream>
using namespace std;

int main() {
    int a = 4, b = 5;
    int maximum = max(a, b);
    while (true) {
        if (maximum % a == 0 && maximum % b == 0) {
            cout << "LCM: " << maximum << endl;
            break;
        }
        maximum++;
    }
}

出力

上記のプログラムを実行すると、次のような結果が得られます。

20

これで LCM の概念と、2つの正の整数の LCM を求める方法が理解できました。続いて、本題である「3つの数の LCM を最大化する」問題の解き方を見ていきます。

問題を解くための手順

N 以下の3つの整数で LCM が最大になる組み合わせは、以下の方針で求められます。

• N が奇数の場合: N、N−1、N−2 の3つを選びます。N と N−2 はどちらも奇数となり互いに素になるため、大きな値のまま LCM を最大化できます。

• N が偶数で、N と N−3 の最大公約数(GCD)が 1 の場合: N、N−1、N−3 の3つを選びます。

• それ以外の場合: N−1、N−2、N−3 の3つを選びます。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void threeNumbersWithMaxLCM(int n) {
    if (n % 2 != 0) {
        // N が奇数の場合
        cout << n << " " << (n - 1) << " " << (n - 2);
    }
    else if (__gcd(n, (n - 3)) == 1) {
        // N が偶数で、N と N−3 が互いに素の場合
        cout << n << " " << (n - 1) << " " << (n - 3);
    }
    else {
        // 上記以外の場合
        cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
    }
    cout << endl;
}

int main() {
    int n = 18;
    threeNumbersWithMaxLCM(n);
    return 0;
}

出力

このプログラムを実行すると、次の結果が出力されます。

17 16 15

入力が 18(偶数)で、18 と 15 の GCD が 3 となるため、条件分岐により 17、16、15 が選ばれています。

なぜこのアルゴリズムが成立するのか

LCM を最大化するには、できるだけ大きい数を選びつつ、選んだ数同士が互いに素(共通の素因数を持たない)であることが理想です。連続する整数は必ず互いに素になるため、「大きい数から順に選ぶ」ことが基本戦略になります。

ただし N が偶数の場合、N と N−2 はどちらも偶数となり共通因数 2 を持ってしまうため、代わりに N−3 を候補に加えます。さらに N と N−3 が互いに素でない場合は、すべてを1つずつ下げた N−1、N−2、N−3 を採用します。この方法なら、条件分岐だけで O(1) で答えを求められます。

まとめ

本チュートリアルでは、LCM の基本概念から、N 以下の3つの整数の LCM を最大化するアルゴリズムまでを解説しました。偶数・奇数の条件分岐による効率的な解法は、競技プログラミングなどでも役立つ考え方です。チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。