Zenn
🦔

【C#アルゴリズム】最小公倍数

2024/11/26に公開
C#
アルゴリズム
tech

はじめに

paiza　、アルゴリズムの本で最大公約数を求めるアルゴリズムについて学んだのでまとめました。

手法

主に以下の二つの手法があります。2のユークリッドの互除法を用いる方法のほうが汎用性が高いです。

  1. 素因数分解を用いる方法
  2. ユークリッドの互除法を用いる方法

1. 素因数分解を用いる方法

手法概要

  • 各数を素因数分解し、共通する素因数の指数の最大値を取り、それらを掛け合わせて最小公倍数を求めます。

例

a = 12, b = 18 の場合：

  • 12 = 2^2 \cdot 3^1
  • 18 = 2^1 \cdot 3^2
  • 素因数 2, 3 の指数の最大値を取る。
    • 2^{\max(2, 1)} = 2^2 = 4
    • 3^{\max(1, 2)} = 3^2 = 9
  • 最小公倍数: 4 \cdot 9 = 36

C#での実装例

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 入力配列を準備
        int[] numbers = { 12, 15, 18 };

        // 素因数とその最大指数を記録する辞書
        Dictionary<int, int> lcmFactors = new Dictionary<int, int>();

        // 各数値を素因数分解し、最大指数を記録
        foreach (var number in numbers)
        {
            var currentFactors = Factorize(number);
            foreach (var item in currentFactors)
            {
                if (!lcmFactors.ContainsKey(item.Key))
                {
                    lcmFactors[item.Key] = 0;
                }
                lcmFactors[item.Key] = Math.Max(lcmFactors[item.Key], item.Value);
            }
        }

        // 最小公倍数を計算
        long lcm = 1;
        foreach (var item in lcmFactors)
        {
            lcm *= (long)Math.Pow(item.Key, item.Value);
        }

        Console.WriteLine($"最小公倍数: {lcm}"); // 180
    }

    // 素因数分解のメソッド
    private static Dictionary<int, int> Factorize(int n)
    {
        Dictionary<int, int> factors = new Dictionary<int, int>();

        // 2 で割り切れる回数を記録
        while (n % 2 == 0)
        {
            if (!factors.ContainsKey(2)) factors[2] = 0;
            factors[2]++;
            n /= 2;
        }

        // 3 以上の奇数で素因数分解
        for (int i = 3; i * i <= n; i += 2)
        {
            while (n % i == 0)
            {
                if (!factors.ContainsKey(i)) factors[i] = 0;
                factors[i]++;
                n /= i;
            }
        }

        // 最後に残った n が素数である場合
        if (n > 1) factors[n] = 1;

        return factors;
    }
}

2. ユークリッドの互除法を用いる方法

手法概要

  • 2つの数 a と b の最小公倍数は、最大公約数 (GCD) を利用して以下の式で求めることができます：
    \text{LCM}(a, b) = \frac{a \cdot b}{\text{GCD}(a, b)}

例

a = 12, b = 18 の場合：

  • 最大公約数: \text{GCD}(12, 18) = 6
  • 最小公倍数:
    \text{LCM}(12, 18) = \frac{12 \cdot 18}{6} = 36

C#での実装例

using System;

class Program
{
    static void Main()
    {
        // 入力配列
        int[] numbers = { 12, 15, 18 };

        // 最小公倍数を求める
        int lcm = numbers[0];
        for (int i = 1; i < numbers.Length; i++)
        {
            lcm = Lcm(lcm, numbers[i]);
        }

        Console.WriteLine($"最小公倍数: {lcm}");
    }

    private static int Gcd(int a, int b)
    {
        while (b != 0)
        {
            int surplus = a % b;
            a = b;
            b = surplus;
        }
        return a;
    }

    private static int Lcm(int a, int b)
    {
        int gcd = Gcd(a, b);
        return a / gcd * b;
    }
}

比較

特徴 素因数分解を用いる方法 最大公約数を利用する方法
計算の仕組み 素因数を列挙して比較する 除算を利用して簡単に計算できる
効率 数が大きい場合には計算コストが高い 非常に効率的
実装の容易さ 複雑 簡単
適用場面 素因数分解が必要な場合 数値が大きい場合や効率が求められる場合

まとめ

  • 素因数分解の方法: 数が小さい場合や、素因数の情報が欲しい場合に適しています。
  • 最大公約数を利用する方法: 最小公倍数を効率的に求めたい場合、特に大きな数に対して有効です。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion