C#で素因数分解

C#で素因数分解するプログラム

コンソール入力から値を受け取り、因数分解後の要素を出力するプログラムです。
今回はC#らしく素因数要素をIEnumerableで返すように実装しています。

Prime.cs

public class Prime{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Console.WriteLine("{0} = {1}", n, string.Join(" x ", PrimeFactors(n)));
    }

    public static IEnumerable<int> PrimeFactors(int n)
    {
        int i = 2;
        int tmp = n;

        while (i * i <= n) //※1
        {
            if(tmp % i == 0){
                tmp /= i;
                yield return i;
            }else{
                i++;
            }
        }
        if(tmp != 1) yield return tmp;//最後の素数も返す
    }
}

実行例1

> 18
18 = 2 x 3 x 3

実行例2

> 2048
2048 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2

実行例3

> 2146654199
2146654199 = 46327 x 46337

※1

素因数分解は、

「合成数 x は p \leq \sqrt{x} を満たす素因子 p をもつ」

という性質を用いて高速に求めることができます。ここではsqrt計算するコストより2乗するコストが安いだろうということでiを2乗した数とnを比較しています。