Zenn
📚

【C#アルゴリズム】最大公約数

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

はじめに

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

手法

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

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

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

手法概要

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

例

12と18の場合:

  • 12 = 2^2 \cdot 3^1
  • 18 = 2^1 \cdot 3^2
  • 共通素因数 2, 3 の指数の最小値を取る。
    • 2^{\min(2, 1)} = 2^1 = 2
    • 3^{\min(1, 2)} = 3^1 = 3
  • 最大公約数: 2 \cdot 3 = 6

C#での実装例

using System;
using System.Collections.Generic;

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

        // 最初の数を素因数分解して初期化
        Dictionary<int, int> gcdFactors = Factorize(numbers[0]);

        // 配列の他の数と共通する素因数の最小指数を計算
        for (int i = 1; i < numbers.Length; i++)
        {
            var currentFactors = Factorize(numbers[i]);
            foreach (var key in new List<int>(gcdFactors.Keys))
            {
                if (currentFactors.ContainsKey(key))
                {
                    gcdFactors[key] = Math.Min(gcdFactors[key], currentFactors[key]);
                }
                else
                {
                    gcdFactors[key] = 0; // 共通素因数がない場合は指数を 0 にする
                }
            }
        }

        // 最大公約数を計算
        int gcd = 1;
        foreach (var item in gcdFactors)
        {
            gcd *= (int)Math.Pow(item.Key, item.Value);
        }

        Console.WriteLine($"最大公約数: {gcd}");　// 3
    }

    // 素因数分解のメソッド
    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 に対し、次の操作を繰り返します：

  1. a を b で割り、余り r を求める。
  2. a = b, b = r と更新。
  3. b = 0 になった時の a が最大公約数。

例

12と18の場合:

  1. 18 \div 12 = 1 余り 6
  2. 12 \div 6 = 2 余り 0
  3. 最大公約数は 6。

C#での実装例

using System;

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

        // 最初の値を初期の最大公約数とする
        int gcd = numbers[0];

        // 配列の他の値と逐次的に最大公約数を計算
        for (int i = 1; i < numbers.Length; i++)
        {
            gcd = Gcd(gcd, numbers[i]);

            // 最大公約数が1になれば、以降の計算は不要
            if (gcd == 1) break;
        }

        Console.WriteLine($"最大公約数: {gcd}"); // 出力: 3
    }

    // ユークリッドの互除法を用いたGCD計算
    private static int Gcd(int a, int b)
    {
        while (b != 0)
        {
            int surplus = a % b;
            a = b;
            b = surplus;
        }
        return a;
    }
}

比較

特徴 素因数分解 ユークリッドの互除法
計算の仕組み 素因数を列挙して比較する 除算と剰余を繰り返す
効率 大きな数には不向き 非常に効率的
実装の容易さ 辞書やリストの操作が必要な場合あり 簡単に実装可能
適用場面 小さな数、素因数が必要な場合に便利 大きな数や計算効率が求められる場合

まとめ

  • 素因数分解の方法: 数が小さい場合や、素因数の情報が欲しい場合に適しています。
  • ユークリッドの互除法: 最大公約数を効率的に求めたい場合、特に大きな数に対して有効です。

おすすめ・参考書籍

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

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

Discussion