最小公倍数（LCM）

GCDを利用して二つの整数の最小公倍数を効率的に求める数学的アルゴリズム

O(log n)

時間計算量

O(1)

空間計算量

中級

難易度

数学的関係

LCM × GCD = a × b

🧮 入力設定

計算対象:

lcm(12, 8)

数学的関係:

LCM = (a × b) / GCD(a, b)

🔗 GCDを利用した効率的な計算

数値 A

数値 B

📚 推奨入力例

🧮

最小公倍数を計算してください

左側の入力パネルから数値を設定し、「LCM計算実行」ボタンを押してください

💻 実装例（JavaScript）

// 最小公倍数（LCM）を効率的に計算
function gcd(a, b) {
    // ユークリッドの互除法でGCDを計算
    while (b !== 0) {
        const remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

function lcm(a, b) {
    // LCM = |a × b| / GCD(a, b)
    if (a === 0 || b === 0) {
        throw new Error("0との最小公倍数は定義されません");
    }
    
    const absA = Math.abs(a);
    const absB = Math.abs(b);
    const gcdValue = gcd(absA, absB);
    
    return (absA * absB) / gcdValue;
}

// オーバーフロー対策版（大きな数値の場合）
function lcmSafe(a, b) {
    if (a === 0 || b === 0) {
        throw new Error("0との最小公倍数は定義されません");
    }
    
    const absA = Math.abs(a);
    const absB = Math.abs(b);
    const gcdValue = gcd(absA, absB);
    
    // (a / gcd) * b の順序で計算（オーバーフロー対策）
    return (absA / gcdValue) * absB;
}

// 複数の数の最小公倍数
function lcmMultiple(...numbers) {
    return numbers.reduce((acc, num) => lcm(acc, num));
}

// 使用例
console.log(lcm(12, 8));           // 24
console.log(lcm(17, 13));          // 221 (互いに素)
console.log(lcm(6, 4));            // 12
console.log(lcm(15, 25));          // 75
console.log(lcm(7, 21));           // 21 (一方が他方の倍数)

// 複数の数の例
console.log(lcmMultiple(4, 6, 8)); // 24

// 分数の通分での利用例
function addFractions(num1, den1, num2, den2) {
    const commonDenominator = lcm(den1, den2);
    const newNum1 = num1 * (commonDenominator / den1);
    const newNum2 = num2 * (commonDenominator / den2);
    const resultNum = newNum1 + newNum2;
    
    // 約分
    const gcdValue = gcd(resultNum, commonDenominator);
    return {
        numerator: resultNum / gcdValue,
        denominator: commonDenominator / gcdValue
    };
}

console.log(addFractions(1, 4, 1, 6)); // { numerator: 5, denominator: 12 }

🎯 最小公倍数の応用と特徴

実世界での応用

• 分数の通分・加減算
• 周期的現象の同期計算
• タスクスケジューリング
• 音楽理論（リズムパターン）
• プログラミング（配列サイズ調整）
• 信号処理（サンプリング周波数）

数学的性質

• LCM(a, b) × GCD(a, b) = a × b
• LCM(a, b) ≥ max(a, b)
• LCM(a, 1) = a
• LCM(a, a) = a
• 交換法則: LCM(a, b) = LCM(b, a)
• 結合法則: LCM(a, LCM(b, c)) = LCM(LCM(a, b), c)

💡 重要な関係: LCMとGCDは相補的な関係にあり、一方を効率的に計算できれば他方も簡単に求められます。この数学的関係を利用することで、複雑な計算を単純化できます。