【C言語】最小公倍数の求め方（３つ以上も可）

このページでは、C言語での「最小公倍数の求め方」について解説していきます。

まずは２つの自然数に対する最小公倍数の「力まかせ」での求め方について解説し、続いて「最大公約数」を利用した最小公倍数の求め方について解説します。

その後、３つ以上の自然数に対する最小公倍数の求め方についても解説していきたいと思います！

上述でも少し触れているように、このページでは最小公倍数を求める対象となる数は自然数であることを前提として解説させていただきます（自然数は 0 を “含まない” ものとします）。

また、最小公倍数を効率よく求めるためには最大公約数を利用するのが手っ取り早いです。最大公約数の求め方については下記ページで解説していますので、最大公約数の求め方をご存知ない方は下記ページを事前に読んでいただくことをオススメします。

【C言語】最大公約数の求め方（ユークリッドの互除法・３つ以上など）

力まかせで最小公倍数を求める

まずは、２つの自然数に対する最小公倍数について解説し、その最小公倍数の求め方について解説していきます。ここでは、最大公約数は利用せず、力まかせに最大公約数を求めていきます。

最小公倍数とは

では、最初に最小公倍数について整理しておきましょう！

２つの自然数における最小公倍数とは、２つの自然数の公倍数における 0 以外の最小の正の数のことを言います。

また、公倍数とは２つの自然数における共通の倍数のことです。さらに、ある自然数に対する倍数とは、その自然数の整数倍の自然数のことを言います。つまり、ある自然数に対する倍数は、必ずその自然数そのもので割り切ることができます。

そして、C言語においては、割り切れるかどうかは剰余演算（%）を行うことで調べることができます。

例えば自然数 a に対し、m が倍数であるかどうかは m % a == 0 が成立するかどうかを調べることで判断できます。剰余演算では、被除数（m）が除数（a）で割り切れる場合、演算結果が必ず 0 になります。

また、自然数 a と自然数 b に対し、m が公倍数であるかどうかは m % a == 0 と m % b == 0 の両方が成立するかどうかを調べることで判断できます。

この２つの式の両方が成立するということは、m は a でも b でも割り切れるということですので、m は a と b の両方に共通する倍数、すなわち公倍数であると言えます。

そして、このページで扱う最小公倍数とは、その公倍数の中で最小の正の数のことを言います。

さらに、この最小公倍数が取りうる値は、２つの自然数の大きい方の数 〜 ２つの自然数の積 の範囲となります。

２つの自然数の大きい方の数 の倍数の中で、２つの自然数の大きい方の数 よりも小さな数は 0 しかありません。なので、２つの自然数の大きい方の数 よりも小さな数で、２つの自然数の公倍数となり得る数は 0 のみです。

ただ、0 は最小公倍数ではないため（最小公倍数とは、２つの自然数の公倍数の “0 以外” の最小の正の数）、結局 ２つの自然数の大きい方の数 よりも小さな数は最小公倍数にはなり得ません。

また、２つの自然数を掛け合わせた結果、つまり ２つの自然数の積 は必ず２つの自然数の公倍数になりますので、最小公倍数は必ず ２つの自然数の積 以下の値となります。

ですので、２つの自然数の最小公倍数が取りうる値は、２つの自然数の大きい方の数 〜 ２つの自然数の積 の範囲となります。

この辺りを考慮しながら、例えば 4 と 6 の最小公倍数について考えてみましょう！

まず、4 と 6 の公倍数は、0・12・24・36・48・・・・と無限に挙げることができるのですが、２つの自然数の大きい方の数 〜 ２つの自然数の積 の範囲の公倍数に絞って考えれば、12・24 の２つのみとなります。

どの数が 4 と 6 の公倍数であるかは、前述の通り 4 と 6 で実際に剰余演算を行ってみることで調べることが可能です。

そして、この２つの数の中から最小のものが最小公倍数となります。今回の場合は 12 ということになりますね！

スポンサーリンク

最小公倍数を力まかせで求める

最小公倍数をプログラムとして解く場合も、結局は上記の例で最小公倍数を求めた時と同様の演算を行えば良いだけです。

要は、剰余演算を利用して２つの自然数の最小の公倍数を見つけ出してやれば良いだけです。

例えば、数を ２つの自然数の大きい方の数 〜 ２つの自然数の積 まで 1 ずつ増加させながら、その数が２つの自然数の公倍数であるかどうかを調べていけば、最初に見つけた公倍数が最小公倍数ということになります（最小公倍数とは で解説したように、最小公倍数は必ず ２つの自然数の大きい方の数 〜 ２つの自然数の積 の範囲内に存在する）。

逆に、数を ２つの自然数の積 〜 ２つの自然数の大きい方の数 まで 1 ずつ減少させながら、その数が２つの自然数の公倍数であるかどうかを調べていけば、最後に見つけた公倍数が最小公倍数ということになります

上記の両方とも、結局は総当たりで力まかせに最小公倍数を見つけ出しているだけなので処理効率は悪いです。なので、特に ２つの自然数の積 が大きな値である場合、最小公倍数を求めるのに時間がかかる可能性があります。

最小公倍数を力まかせで求める関数

ここまで解説してきた内容に基づいて作成した「最小公倍数を力まかせに求める関数」は、下記ソースコードにおける lcm 関数となります。

lcm 関数は、引数 a と引数 b で与えられる２つの自然数の最小公倍数を返却値として求める関数になります。

lcm 関数内部では、i を ２つの自然数の大きい方の数 〜 ２つの自然数の積 まで 1 ずつ増加させ、最初に見つけた a と b の公倍数となる i を最小公倍数として返却するようにしています。

#include <stdio.h>

unsigned int lcm(unsigned int a, unsigned int b) {
    unsigned int big;

    if (a == 0 || b == 0) {
        printf("a or b is 0!!!\n");
        return 0;
    }

    if (a > b) {
        big = a;
    } else {
        big = b;
    }

    unsigned int ans = 0;
    for (unsigned int i = big; i <= a * b; i++) {
        if (i % a == 0 && i % b == 0) {
            ans = i;
            break;
        }
    }

    return ans;
}

int main(void) {
    
    unsigned int x = 776;
    unsigned int y = 1261;

    printf("lcm(%u, %u) = %u\n", x, y, lcm(x, y));

    return 0;

}

最小公倍数は 0 にはなり得ないため、引数に 0 が指定された場合は最小公倍数を求めることができません（0 の倍数は 0 のみなので公倍数も 0 のみになってしまう）。この場合は、とりあえず printf でエラー表示し、0 を返却するようにしています。

この点に関しては以降で紹介する関数も同様になります。

最大公約数を利用して最小公倍数を求める

先程紹介した手順でも最小公倍数を求めることは可能ですが、要は最小公倍数となりうる全ての候補の数に対して最小公倍数であるかどうかを調べていく方法ですので、処理効率が悪いです。

ただ、最小公倍数は最大公約数を利用して求めることができ、最大公約数はユークリッド互除法で効率的に求めることができます。そのため、最大公約数を利用することで、力まかせに求めるよりも効率よく最小公倍数を求めることができます。

次は、その最大公約数を利用して２つの自然数の最小公倍数を求めていきたいと思います！

スポンサーリンク

最大公約数を利用した最小公倍数の求め方

２つの自然数の最小公倍数は、その２つの自然数の最大公約数を利用して下記の式により求めることができます。

最小公倍数 = １つ目の自然数 * ２つ目の自然数 / 最大公約数

つまり、２つの自然数の数を掛け合わせ、それを最大公約数で割ってやれば良いだけです。簡単ですね！

ただ、上記の計算を行うためには２つの自然数の最大公約数を求めてやる必要があります。この最大公約数の求め方については下記のページで紹介していますので、最大公約数の求め方をご存知ない方は下記ページを参照していただければと思います。

【C言語】最大公約数の求め方（ユークリッドの互除法・３つ以上など）

上記の式の計算を行う上での注意点を１つ挙げておくと、１つ目の自然数 * ２つ目の自然数 を計算する際に「桁あふれ（オーバーフロー）」が発生しないように注意してください。

C言語では、計算結果も変数同様に特定の型のデータとして扱われます。例えば、２つの自然数を unsigned int 型の変数として扱う場合、掛け算結果も unsigned int 型として扱われます。そのため、 １つ目の自然数 * ２つ目の自然数 の結果が unsigned int 型で扱える値の最大値を超えた場合、桁あふれが発生し、計算結果がおかしくなってしまいます。

桁あふれの発生を考慮した場合、上記の式そのままではなく、次のように式変形を行なって最小公倍数を求める方が無難です。

最小公倍数 = １つ目の自然数 / 最大公約数 * ２つ目の自然数

先に １つ目の自然数 / 最大公約数 を計算することで、最大公約数 が 2 以上の場合は計算結果が小さくなります。そして、小さくなった結果に対して ２つ目の自然数 を掛けることになるので、そのまま １つ目の自然数 * ２つ目の自然数 を計算するよりも桁あふれが発生しにくくなります。

ただ、桁があふれが発生しにくくはなるものの、完全に桁あふれを防ぐことができるというわけではないです。桁あふれをもっと発生しにくくするためには、自然数を扱う変数や引数の型に、もっと大きな数を扱える型を選ぶ必要があります。

最大公約数を利用して最小公倍数を求める関数

ここまで解説してきた内容に基づいて作成した「最大公約数を利用して最小公倍数を求める関数」は、下記の lcm になります。

#include <stdio.h>

unsigned int gcd_r(unsigned int a, unsigned int b) {
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }

    return gcd_r(b, a % b);
}

unsigned int gcd(unsigned int x, unsigned int y) {
    unsigned int big, small;

    if (x > y) {
        big = x;
        small = y;
    } else {
        big = y;
        small = x;
    }

    return gcd_r(big, small);
}

unsigned int lcm(unsigned int a, unsigned int b) {
    unsigned int big;

    if (a == 0 || b == 0) {
        printf("a or b is 0!!!\n");
        return 0;
    }

    return a / gcd(a, b) * b;
}

int main(void) {
    
    unsigned int x = 776;
    unsigned int y = 1261;

    printf("lcm(%u, %u) = %u\n", x, y, lcm(x, y));

    return 0;
}

lcm 関数では 最大公約数を利用した最小公倍数の求め方 で紹介した式をそのまま実行しているだけですが、最大公約数を求めるのに gcd 関数を利用しています。さらに、その gcd 関数からは gcd_r 関数を利用して最小公約数を求めています。

これらの gcd 関数と gcd_r は下記ページの 再帰呼び出しでユークリッドの互除法を行う関数 をそのまま利用しています。

【C言語】最大公約数の求め方（ユークリッドの互除法・３つ以上など）

３つ以上の自然数の最小公倍数を求める

ここまで２つの自然数に対する最小公倍数の求め方について解説してきましたが、次は３つ以上の自然数に対する最小公倍数の求め方について解説していきたいと思います。

下記ページで３つ以上の自然数の最大公約数の求め方について解説していますが、最小公倍数の場合もほぼ同様で、２つの自然数の最小公倍数を段階的に繰り返し求めていくことで、３つ以上の最小公倍数を求めることが可能です。

【C言語】最大公約数の求め方（ユークリッドの互除法・３つ以上など）

スポンサーリンク

３つ以上の自然数の最小公倍数の求め方

まず、n 個の自然数の最小公倍数を求める関数を lcm_n としたいと思います。この時、n = 3 の場合、つまり 3 個の自然数の最小公倍数を求める lcm_3 には下記が成立します。

lcm_3(a, b, c) = lcm_2(lcm_2(a, b), c)

つまり、３つの自然数に対する最小公倍数は、そのうちの２つの自然数に対する最小公倍数を求め、さらに、その 結果と残った１つの自然数に対する最小公倍数を求めることで得ることができます。

ということは、２つの自然数の最小公倍数を求める関数さえ用意できれば、その関数を実行していくことで３つの自然数の最小公倍数も求めることができるということになります。

２つの自然数の最小公倍数を求める関数に関しては、下記で紹介した lcm 関数（lcm 関数から実行されている関数も必要）がそのまま使えます。

• 最小公倍数を力まかせで求める関数
• 最大公約数を利用して最小公倍数を求める関数

４つ以上の自然数の最小公倍数に関しても同様で、２つの自然数の最小公倍数を求めていくことで求めることができます。

lcm_n(a, b, c, d,...) = lcm_2(... lcm_2(lcm_2(lcm_2(a, b), c), d) ...)

上記の式を見ると難しそうに思えますが、要は n 個の自然数の先頭の２つの自然数の最小公倍数を求め、その結果と次の自然数の最小公倍数を求め、その結果と次の自然数の最小公倍数を求め…、といった処理を n - 1 回分繰り返せば良いだけです。最後に求めた最小公倍数が、n 個の自然数の最小公倍数となります。

３つ以上の自然数の最小公倍数を求める関数

ここまで解説してきた内容に基づいて作成した「３つ以上の自然数の最小公倍数を求める関数」は下記の lcm_n となります。

lcm_n 関数は n 個の自然数の最小公倍数を求める関数であり（n は引数で与えられる）、n 個の自然数は配列 nums に格納されているものとしています。

また、lcm 関数は 最大公約数を利用して最小公倍数を求める関数 で紹介したものと全く同じ関数となります。さらに、lcm 関数内では最大公約数を求めるために、最大公約数を利用して最小公倍数を求める関数 で紹介した gcd 関数および gcd_r 関数を利用しています。

#include <stdio.h>

unsigned int gcd_r(unsigned int a, unsigned int b) {
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }

    return gcd_r(b, a % b);
}

unsigned int gcd(unsigned int x, unsigned int y) {
    unsigned int big, small;

    if (x > y) {
        big = x;
        small = y;
    } else {
        big = y;
        small = x;
    }

    return gcd_r(big, small);
}

unsigned int lcm(unsigned int a, unsigned int b) {
    unsigned int big;

    if (a == 0 || b == 0) {
        printf("a or b is 0!!!\n");
        return 0;
    }

    return a / gcd(a, b) * b;
}

unsigned int lcm_n(unsigned int nums[], unsigned int size) {

    if (size == 0) {
        return 0;
    }

    unsigned int ans = nums[0];
    for (int i = 1; i < size; i++) {
        ans = lcm(ans, nums[i]);
    }

    return ans;
}

int main(void) {

    unsigned int nums[] = {
        776, 1843, 291, 970, 2037
    };

    printf("%u\n", lcm_n(nums, sizeof(nums) / sizeof(nums[0])));

    return 0;
}

lcm_n 関数では、２つの自然数の最小公倍数を lcm 関数で求めることを繰り返すことで、n 個の自然数の最小公倍数 ans を求めています。

この lcm_n 関数に関しても、下記ページの ３つ以上の自然数の最大公約数を求める関数 で紹介している gcd_n 関数と作りはほとんど同じです。なので、下記ページを読んでくださった方であれば、lcm_n 関数の動作についても理解していただけるのではないかと思います。

【C言語】最大公約数の求め方（ユークリッドの互除法・３つ以上など）

一応このページでも解説しておくと、まず for ループに入る直前に ans = nums[0] を実行し、さらに for ループの最初の繰り返しにおいて ans = lcm(ans, nums[1]) を行うことで、ans と nums[1] の最小公倍数を求めています。

ここで、ans には元々 nums[0] の値が格納されているので、結局ここで求められるのは nums[0] と nums[1] の２つの自然数の最小公倍数ということになります。そしてその最小公倍数で ans を更新しています。

さらに、次の繰り返しにおいて ans = lcm(ans, nums[2]) を行うことで、ans と nums[2] の最小公倍数を求めています。

ここで、ans には元々 nums[0] と nums[1] の２つの自然数の最小公倍数が格納されているので、結局ここで求められるのは nums[0] と nums[1] と nums[2] の３つの自然数の最小公倍数ということになります。そしてその最小公倍数で ans を更新しています。

こんな感じで、i に対する for ループの中で ans = lcm(ans, nums[i]) が実行される際には、i + 1 個の自然数の最小公倍数が求められることになります。

そして、for ループの最後には i が n - 1 の状態で  ans = lcm(ans, nums[i]) が実行されるわけですから、最終的には n 個の自然数の最小公倍数が求められることになります。

そしてその最小公倍数が格納される変数 ans を最後に return するようにすることで、n 個の自然数の最小公倍数を返却できるようにしています。

また、main 関数では求めたい個数の自然数をあらかじめ配列 nums に格納しておき、引数に配列 nums と nums の要素数を指定して lcm_n 関数を実行して最小公倍数を求めています。

要素数を求める際に使用している sizeof をご存知ない方は、是非下記ページを読んでみてください。sizeof は配列の要素数を求めるだけでなく、型のサイズ等を調べる際にも有用な演算子になります。

【C言語】sizeof演算子とは？sizeof演算子を利用するメリットは？

まとめ

このページでは、C言語での「最小公倍数の求め方」について解説しました！

力まかせで最小公倍数を求める で解説したように、最小公倍数がどんな数であるかを理解しておけば、力まかせに総当たりで最小公倍数を求めることが可能です。

また、最大公約数を利用して最小公倍数を求める で解説したように、力まかせではなく最大公約数を利用して最小公倍数を求めることも可能です。ユークリッドの互除法等を用いて最大公約数を効率的に求めることで、最小公倍数も効率的に求めることができます。

さらに、３つ以上の自然数の最小公倍数を求める でも解説したように、２つの自然数の最小公倍数を求める関数さえ用意できれば、その関数を利用して３つ以上の自然数の最小公倍数も簡単に求めることができます。

特に最大公約数を利用する場合、変数等を式に当てはめれば良いだけなので簡単に最小公倍数を求めることができます（最大公約数を求める関数が必要ではありますが）。是非この求め方はしっかり覚えておきましょう！