search
LoginSignup
10

More than 5 years have passed since last update.

posted at

updated at

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
10