Edited at

C#で素因数分解

More than 3 years have passed since last update.


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を比較しています。