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

この記事では、N以下の3つの整数のうち、LCM(最小公倍数)が最大になる組み合わせを見つける方法について解説します。

問題の概要

整数 N が与えられたとき、N 以下の範囲から3つの整数を選び、その3数の最小公倍数(LCM)ができるだけ大きくなるような組み合わせを求めるのが課題です。

実は、最大のLCMを与える3つの整数は必ず N に近い値の中から選ばれることが知られています。そのため、N・N−1・N−2・N−3 という4つの候補だけで場合分けすれば、効率よく答えを導き出すことができます。

アルゴリズムの考え方

連続する2つの整数は互いに素(最大公約数が1)であるため、なるべく大きい数同士を組み合わせるほどLCMは大きくなります。ただし、N が偶数の場合は N と N−2 がともに偶数となり共通因数の 2 を持つため、単純に積を取ることができません。そこで、次のように場合分けを行います。

• N が奇数の場合: N・N−1・N−2 は互いに素となるため、この3数の積が最大のLCMになります。
• N が偶数かつ gcd(N, N−3) = 1 の場合: N・N−1・N−3 を選択します。
• N が偶数かつ gcd(N, N−3) ≠ 1 の場合(N が3の倍数): N−1・N−2・N−3 を選択します。

C++での実装例

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

// 与えられた値以下でLCMが最大となる3つの整数を求める関数
void findMaximumLCM(int n) {
    if (n % 2 != 0) {
        cout << n << " " << (n - 1) << " " << (n - 2);
    }
    else if (__gcd(n, (n - 3)) == 1) {
        cout << n << " " << (n - 1) << " " << (n - 3);
    }
    else {
        cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
    }
}

int main() {
    int number = 34;
    findMaximumLCM(number);
    return 0;
}

実行結果

34 33 31

出力の解説

入力が 34 の場合、34 は偶数であり、gcd(34, 31) = 1 が成り立つため「34 33 31」が出力されます。このときのLCMは 34 × 33 × 31 = 34812 となり、34 以下の3つの整数の組み合わせの中で最大の値になります。

まとめ

本記事では、N以下の3つの整数のうちLCMが最大になる組み合わせを求めるアルゴリズムをC++で紹介しました。候補となる組み合わせはわずか3パターンしかないため、計算量は GCD 計算の O(log N) 程度に抑えられ、非常に高速に動作します。競技プログラミングでも応用される考え方なので、ぜひ理解しておきましょう。