C#で最小公倍数を求める

今回は最小公倍数を計算するプログラムを作成します。

突然ですが、分数の足し算は好きですか？

足し算よりもかけ算のほうが普通は難しいのですが、分数の場合はそうではありません。分数のかけ算は分母同士、分子同士を掛け合わせるだけです。ところが分数の足し算は通分という作業が必要です。当時小学生だった私はこれがとても嫌だったのです。

通分するときは分母を計算しようとしている分母の最小公倍数にしなければなりません。2と3の最小公倍数であれば6であることはすぐにわかるのですが、14と18の最小公倍数なんていわれるとすぐには計算できません。

14の倍数：14, 28, 42, 56, 70, 84, 98, 112, 126, 140,
18の倍数：18, 36, 54, 72, 90, 108, 126, 144, 162, 180,

だから答えは126。教科書どおりやろうとするとこうなります。

もっと効率よく計算する方法はないのでしょうか？　この方法を教えてくれるのは中学1年生になってからです。簡単な方法だったので、どうして小学校で教えてくれないのかと怒りでいっぱいになったことがあります（ちょっと大袈裟か）。

Contents

1 効率が悪い最小公倍数をもとめるプログラム
2 最小公倍数を求める
3 最大公約数を求める

効率が悪い最小公倍数をもとめるプログラム

まずは効率が悪い方法から紹介します。

14の倍数をリストに格納しておき、そのなかから18の倍数を探すというやり方です。最初にリストに格納すべき個数ですが、以下のように考えます。

14×18は最小ではないけれども14と18の公倍数である（14×18は14の18倍であり18の14倍だから）
そこで14×18以下の14の倍数を取得する

class Program
{
    static void Main()
    {
        int a = 14;
        int b = 18;

        List<int> vs = new List<int>();
        for (int i = 1; a * i <= a * b; i++)
            vs.Add(a * i);

        int answer = 0;
        foreach (int i in vs)
        {
            if (i % b == 0)
            {
                answer = i;
                Console.WriteLine(i);
                break;
            }
        }
        Console.WriteLine(answer);
    }
}

class Program

{

static void Main()

{

int a = 14;

int b = 18;

List<int> vs = new List<int>();

for (int i = 1; a * i <= a * b; i++)

vs.Add(a * i);

int answer = 0;

foreach (int i in vs)

{

if (i % b == 0)

{

answer = i;

Console.WriteLine(i);

break;

}

Console.WriteLine(answer);

}

このやり方は効率が悪いです。14と18という比較的小さな数なのですぐに処理は終わりますが、巨大な数でしかも互いに素である場合、無駄に計算させられるだけでなく、それだけ多くの個数の倍数をリストに格納しなければならないのでメモリーも浪費することになります。

最小公倍数を求める

そこで中学校1年生のときに数学で教えてもらった方法を使います。

14, 18はともに素数2で割り切れる。2で割ると7と9
7と9は互いに素である。
2と7と9を掛け合わせた126が最小公倍数

素数2で割ると一発で終わってしまったので別の例を示します。

48 と 64 の最小公倍数を考える
48 と 64 はともに素数2で割り切れる。2で割ると 24 と 32
24 と 32 はともに素数2で割り切れる。2で割ると 12 と 16
12 と 16 はともに素数2で割り切れる。2で割ると 6 と 8
6 と 8はともに素数2で割り切れる。2で割ると 3 と 4
3 と 4 は互いに素である。
2 と 2 と 2 と 2 と 3 と 4 を掛け合わせた 192 が 48と64の最小公倍数である

割るときは最小の素数からやらないといけないわけではありません。両方とも16の倍数であることに気づいたのであれば
48 と 64 はともに16で割り切れる。16で割ると 3 と 4
3 と 4 は互いに素である。
16 と 3 と 4 を掛け合わせた 192 が48と64の最小公倍数である

こっちのほうがよいです。

また3つ以上の場合は以下のようにします。

14 と 48 と 64 との最小公倍数を考える
14 と 48 と 64 はともに2で割り切れる。2で割ると 7 と 24 と 32
24 と 32 は 8 で割り切れる。割り切れるものだけ8で割ると 7 と 3 と 4
これ以上、2つ以上の数を割りきることができる数は存在しない
2 と 8 と 7 と 3 と 4 を掛け合わせた 1344 が 14と48と64との最小公倍数である

ではこの方法でプログラミングしてみることにします。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.WriteLine("複数の2以上の自然数を半角スペースで区切って入力してください");
        try
        {
            int[] vs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            Console.WriteLine(GetLeastCommonMultiple(vs));
        }
        catch
        {
            Console.WriteLine("不正な入力です");
        }
    }

    static int GetLeastCommonMultiple(int[] vs)
    {
        // 1や0、負数は取り除く
        // その結果、配列の長さが2に満たない場合は例外を投げる
        vs = vs.Where(x => x > 1).ToArray();

        if (vs.Length < 2)
            throw new Exception();

        int div = 2; // 最初は2で割れるかを調べる
        List<int> divs = new List<int>();

        while (true)
        {
            // ふたつ以上の数がdivで割り切ることができるなら割り切れるものだけ割る
            // 割り切ることができない場合はdivをインクリメントする
            // それによって2番目に大きな数よりもdivのほうが大きくなったとき
            // 割り切ることができる数は今後見つからないと判断してループを抜ける
            if (vs.Count(x => x % div == 0) > 1)
            {
                var a = vs.Where(x => x % div == 0).Select(x => x / div);
                var b = vs.Where(x => x % div != 0);
                vs = a.Union(b).ToArray();
                divs.Add(div);
            }
            else
                div++;

            // 2番目に大きな数を取得する
            // そのためにソートして最後から2番目の要素を取得する
            Array.Sort(vs);
            if (vs[vs.Length - 2] < div)
                break;
        }

        int answer = 1;
        foreach (int i in divs)
            answer *= i;
        foreach (int i in vs)
            answer *= i;

        return answer;
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

Console.WriteLine("複数の2以上の自然数を半角スペースで区切って入力してください");

try

{

int[] vs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

Console.WriteLine(GetLeastCommonMultiple(vs));

}

catch

{

Console.WriteLine("不正な入力です");

}

static int GetLeastCommonMultiple(int[] vs)

{

// 1や0、負数は取り除く

// その結果、配列の長さが2に満たない場合は例外を投げる

vs = vs.Where(x => x > 1).ToArray();

if (vs.Length < 2)

throw new Exception();

int div = 2; // 最初は2で割れるかを調べる

List<int> divs = new List<int>();

while (true)

{

// ふたつ以上の数がdivで割り切ることができるなら割り切れるものだけ割る

// 割り切ることができない場合はdivをインクリメントする

// それによって2番目に大きな数よりもdivのほうが大きくなったとき

// 割り切ることができる数は今後見つからないと判断してループを抜ける

if (vs.Count(x => x % div == 0) > 1)

{

var a = vs.Where(x => x % div == 0).Select(x => x / div);

var b = vs.Where(x => x % div != 0);

vs = a.Union(b).ToArray();

divs.Add(div);

}

else

div++;

// 2番目に大きな数を取得する

// そのためにソートして最後から2番目の要素を取得する

Array.Sort(vs);

if (vs[vs.Length - 2] < div)

break;

}

int answer = 1;

foreach (int i in divs)

answer *= i;

foreach (int i in vs)

answer *= i;

return answer;

}

最大公約数を求める

最大公約数を求めるプログラムも作成してみることにします。3つ以上の最大公約数を求める場合はすべての数を割りきることができる数を探して割りきることができた数をすべて掛け合わせます。

48 と 64 と 108 の最大公約数を考える
48 と 64 と 108 はすべて 2 で割り切れる。2で割ると 24 と 32 と 54
24 と 32 と 54 はすべて 2 で割り切れる。2で割ると 12 と 16 と 27
これ以上、すべての数を割りきることができる数は存在しない
2 と 2 を掛け合わせた 4 が 48 と 64 と 108 の最大公約数である

class Program
{
    static void Main()
    {
        Console.WriteLine("複数の2以上の自然数を半角スペースで区切って入力してください");
        try
        {
            int[] vs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            Console.WriteLine(GetGreatestCommonDivisor(vs));
        }
        catch
        {
            Console.WriteLine("不正な入力です");
        }
    }

    static int GetGreatestCommonDivisor(int[] vs)
    {
        // 配列の長さが2に満たない場合や0または負数が含まれている場合は例外を投げる
        if (vs.Length < 2 || vs.Count(x => x < 1) > 0)
            throw new Exception();

        int div = 2;
        List<int> divs = new List<int>();

        while (true)
        {
            if (vs.Count(x => x % div == 0) == vs.Length)
            {
                vs = vs.Select(x => x / div).ToArray();
                divs.Add(div);
            }
            else
                div++;

            Array.Sort(vs);
            if (vs[vs.Length - 2] < div)
                break;
        }

        int answer = 1;
        foreach (int i in divs)
            answer *= i;

        return answer;
    }
}

class Program

{

static void Main()

{

Console.WriteLine("複数の2以上の自然数を半角スペースで区切って入力してください");

try

{

int[] vs = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

Console.WriteLine(GetGreatestCommonDivisor(vs));

}

catch

{

Console.WriteLine("不正な入力です");

}

static int GetGreatestCommonDivisor(int[] vs)

{

// 配列の長さが2に満たない場合や0または負数が含まれている場合は例外を投げる

if (vs.Length < 2 || vs.Count(x => x < 1) > 0)

throw new Exception();

int div = 2;

List<int> divs = new List<int>();

while (true)

{

if (vs.Count(x => x % div == 0) == vs.Length)

{

vs = vs.Select(x => x / div).ToArray();

divs.Add(div);

}

else

div++;

Array.Sort(vs);

if (vs[vs.Length - 2] < div)

break;

}

int answer = 1;

foreach (int i in divs)

answer *= i;

return answer;

}

効率が悪い最小公倍数をもとめるプログラム

最小公倍数を求める

最大公約数を求める

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ