C++で2つのフィボナッチ数の最小公倍数（LCM）を求めるプログラム

はじめに

この記事では、2つの整数 N と M が与えられたときに、N番目とM番目のフィボナッチ数を求め、その最小公倍数（LCM：Least Common Multiple）を計算するC++プログラムの作成方法を解説します。

問題の説明

まず N 番目と M 番目のフィボナッチ数をそれぞれ求めます。続いて、その2つの数値の最小公倍数を計算し、結果として返します。

フィボナッチ数とは

フィボナッチ数とは、最初の2項が 0 と 1 で構成され、以降は「直前の2つの数の和」が順に並んでいく数列です。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…

具体例で問題を理解する

入力： N = 4, M = 9

出力： 42

解説

• 4番目のフィボナッチ数は 2
• 9番目のフィボナッチ数は 21
• 2 と 21 の最小公倍数は 42

解法のアプローチ

この問題は、次の2ステップで解くことができます。

1. N 番目と M 番目のフィボナッチ数をそれぞれ計算する
2. 得られた2つの数値の最小公倍数（LCM）を求めて返す

サンプルプログラム

#include <iostream>
using namespace std;

// N番目のフィボナッチ数を求める関数
long int fibo(int N){
    long int a = 0, b = 1, c;
    for(int i = 2; i < N; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

// 2つの数の最小公倍数（LCM）を求める関数
int findLCM(int a, int b){
    int max, step, lcm;
    lcm = 0;
    if(a > b)
        max = step = a;
    else
        max = step = b;
    while(1) {
        if(max % a == 0 && max % b == 0) {
            lcm = max;
            break;
        }
        max += step;
    }
    return lcm;
}

// フィボナッチ数同士のLCMを計算する関数
int CalcFiboLCM(int N, int M) {
    int fiboN = fibo(N);
    int fiboM = fibo(M);
    return findLCM(fiboN, fiboM);
}

int main() {
    int N = 5, M = 14;
    cout << "2つのフィボナッチ数の最小公倍数は " << CalcFiboLCM(N, M);
    return 0;
}

コードの解説

• fibo関数： 反復処理によって N 番目のフィボナッチ数を効率よく計算します。
• findLCM関数： 大きい方の数からスタートし、両方の数で割り切れる値が見つかるまで順に増加させて最小公倍数を探索します。
• CalcFiboLCM関数： 上記2つの関数を組み合わせて、フィボナッチ数同士のLCMを計算します。

出力

2つのフィボナッチ数の最小公倍数は 699

この例では、5番目のフィボナッチ数が 3、14番目のフィボナッチ数が 233 となります。3 と 233 は互いに素であるため、最小公倍数は 3 × 233 ＝ 699 です。

効率化のヒント：GCDを活用する

上記の findLCM 関数は候補となる数を順に増やしながら探索するため、扱う数が大きくなると処理時間が長くなります。実務では、最大公約数（GCD）を利用して「LCM(a, b) ＝ a × b ÷ GCD(a, b)」という公式で求めるのが一般的です。

#include <numeric>

long long calcLCM(long long a, long long b){
    return a / std::gcd(a, b) * b; // C++17以降のstd::gcdを使用
}

この方法であれば探索ループが不要となり、大きな数でも高速かつオーバーフローのリスクを抑えながら最小公倍数を計算できます。

まとめ

C++では、フィボナッチ数の生成と最小公倍数の計算という2つの基本的なアルゴリズムを組み合わせることで、2つのフィボナッチ数のLCMを簡単に求められます。小さな入力にはシンプルな実装で十分ですが、大きな数を扱う場合はGCDを利用した効率的な手法を採用しましょう。