C#で素因数分解を行ってみる！

素因数分解とは、正の整数を素数の積の形で表すことです。数学的な概念ですが、プログラムでも役立つ（実際使う）シーンもあります。
C#で素因数分解を行うための関数を実装する方法を解説します。

素因数分解する関数の作成

まず、与えられた数値を素因数分解するための関数を紹介します。この関数は、2と奇数で割り切れる限り割り続け、最終的に素因数をリストとして返します。

static List<int> PrimeFactorization(int number)
{
    List<int> factors = new List<int>();

    // 2で割り切れる限り、2を追加
    while (number % 2 == 0)
    {
        factors.Add(2);
        number /= 2;
    }

    // 奇数で割り切れる限り、それを追加
    for (int i = 3; i <= Math.Sqrt(number); i += 2)
    {
        while (number % i == 0)
        {
            factors.Add(i);
            number /= i;
        }
    }

    // 最後に残った数が素数なら、それを追加
    if (number > 2)
    {
        factors.Add(number);
    }

    return factors;
}

関数の解説

• 2での割り算:
  最初に、与えられた数値が2で割り切れる限り2で割り続け、その結果をリストに追加します。これは、素数2が素因数分解において最も基本的な要素であるためです。

• 奇数での割り算:
  次に、3から始まる奇数で割り切れるかをチェックします。3、5、7、…と順に割り算を行い、割り切れる場合はその数をリストに追加し、数値を更新します。

• 最後に残った数:
  ループを終えた後、もし残っている数が2より大きければ、それは素数なのでその数自体をリストに追加します。

このようにして、与えられた数値の素因数をすべてリストに格納することができます。

関数の呼び出し

次に、この関数を利用して数値を素因数分解してみましょう。以下のコードでは、数値60を素因数分解しています。

static void Main(string[] args)
{
    List<int> factors = PrimeFactorization(60);
    Console.WriteLine("素因数：" + string.Join(",", factors));
}

実行結果

このコードを実行すると、数値60の素因数である2, 3, 5が以下のように出力されます：

素因数：2,2,3,5

まとめ

素因数分解は数学的にはシンプルな概念ですが、プログラムとして実装することも可能です。C#では、リストとループを使うことで効率的に素因数分解を行うことができます。