14
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

C#で素因数分解

Last updated at Posted at 2015-04-24

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

14
10
0

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
  3. You can use dark theme
What you can do with signing up
14
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?