【C#】素因数分解をするプログラムを作成してみる

はじめに

今回は素因数分解するプログラムを作成してみようと思います。

素因数図分解というのは $12= 2^2 * 3^1$ のように分解することですね。

早速みていきましょう。

はじめに
方針
コード
使い方
さいごに

方針

以下の手順を踏むと素因数分解することができます。

整数nを $\sqrt{n}$ 以下の素数で小さい方から割れるまで割る
値が1以外ならそれも素因数とする
割った素数とその回数を素因数として出力する

コード

public static Dictionary<long, long> PrimeFactorization(long n)
{
    var result = new Dictionary<long, long>();

    for (long i = 2; i * i <= n; i++)
    {
        if (n % i != 0) continue;
        long exponents = 0;

        // 割り続ける
        while (n % i == 0)
        {
            exponents++;
            n /= i;
        }

        result[i] = exponents;
    }

    // 素数が残っている場合
    if (n != 1) result[n] = 1;
    return result;
}

使い方

static void Main(string[] args)
{
    var n = 12;

    var results = PrimeFactorization(n);

    StringBuilder builder = new StringBuilder($"{n}:");
    foreach (var item in results)
    {
        for (int i = 0; i < item.Value; i++)
            builder.Append($" {item.Key}");
    }

    Console.WriteLine(builder.ToString());      // 12 : 2 2 3
}