Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
8
Help us understand the problem. What is going on with this article?
@y_miyoshi

C#で素因数分解

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

8
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
8
Help us understand the problem. What is going on with this article?