素因数分解プログラム - 夜風のMixedReality

本日の１日１問プログラミング学習枠です。

〇お題

問題: 素因数分解

与えられた整数を素因数分解するプログラムを作成してみてください。素因数分解は、与えられた整数を素数の積に分解するプロセスです。たとえば、整数 12 は素因数分解すると 2 × 2 × 3 となります。

プログラムは以下の要件を満たす必要があります：

ユーザーから整数を入力として受け取ります。入力された整数を素因数分解し、結果を表示します。分解された素因数とその指数を示す形式で結果を表示します。たとえば、12 は "2² * 3" と表示されます。この問題を解決するプログラムを作成し、異なる整数に対してテストしてみてください。また、エラーハンドリングを行い、負の整数に対しても適切に対処できるように考慮することがおすすめです。

〇筆者の回答

素因数分解とは、与えられた数を構成する素数で分解することです。

例えば8の場合は2という素数で分解すると2³＝2×2×2=8というように分解できます。

また18の場合は2×3²=2×3×3というように分解できます。

つまり最小の素数である２から割り切れるだけ割っていけば分解できるというようになります。

今回は次のような回答をしました。

using System;

                    
public class Program
{
    public static void Main()
    {
        int input = 84;
        
        Console.WriteLine(PrimeFactorization( input));
    }
    public static string PrimeFactorization(int input)
    {
        string result = "";
        int[] multiplier = new int[input];
        for(int i = 2 ; i<= input ; i++)//最小素数の２から割っていく
        {
            while(input % i == 0 && input != 0)//iで割り切れなくなるorOになるまで
            {
                input /= i; 
                multiplier[i] += 1;        
            }
            if(multiplier[i]!=0 && result != "")//すでに何か記入されている場合
            {
                result += "*";
            }
            switch(multiplier[i])
            {
                case 0:             //multiplier[i] ==0 の場合はiという素因数無し
                    break;
                case 1: //multiplier無し
                    result += i;
                    break;
                default :
                    result += i+ "^" + multiplier[i];
                    break;
            }
        }
        return result;
        
    }   
}

筆者の懸念点としては入力値が大きいほどwhile文の計算量が増えるため無駄が多く、"入力値が素数かどうか？入力値の半分までの素数で計算"ということができれば最小の計算量になるとは思えますが、素数を計算する処理数の方が大きくなる気がしてこの回答をしました。

〇ChatGPTの評価

提供されたコードは、素因数分解を行うための効果的なアプローチを取っており、正確な結果を生成しています。以下はコードの評価と改善点です：

評価:

素因数分解の正確性: コードは、与えられた整数を正確に素因数分解しています。結果は素因数とその指数の形式で表示されています。

エラーハンドリング: 入力値が負の数の場合にエラーハンドリングが行われています。

改善点:

性能向上: 懸念点として挙げられた通り、大きな入力値に対しては計算量が増加し、無駄が多くなります。最も効率的なアプローチは、入力値が素数かどうかを判定し、その後の計算を最小限に抑えることです。素数を計算する処理数が増えても、入力値の素数判定を行うプロセスがより効率的です。これにより、素数でない場合の無駄な計算が減少します。

素数判定: 入力値が素数かどうかを判定する部分が現在のコードには含まれていません。この部分を追加することで、より効率的な素因数分解を実現できます。

提供されたコードは、素因数分解を行う基本的なアプローチにおいて 85 点から 90 点の評価を受けるでしょう。改善点に対処することで、さらに高い点数を獲得できるでしょう。また、素数判定のためのコードを追加することが、性能向上に役立つでしょう。
using System;

public class Program
{
    public static void Main()
    {
        int input = 84;

        Console.WriteLine(PrimeFactorization(input));
    }

    public static string PrimeFactorization(int input)
    {
        if (input <= 1)
        {
            return "1以下の整数には素因数分解がありません。";
        }

        string result = "";
        int divisor = 2;

        while (input > 1)
        {
            int count = 0;

            while (input % divisor == 0)
            {
                input /= divisor;
                count++;
            }

            if (count > 0)
            {
                if (result != "")
                {
                    result += " * ";
                }

                result += divisor;

                if (count > 1)
                {
                    result += "^" + count;
                }
            }

            divisor++;
        }

        return result;
    }
}

改善されたコードを見るとfor文ではなく２重のwhile文でinputが割り切れるまで、効率的に処理されていることがわかります。

配列ではなく、divisorという変数になっておりより効率化されています。

基本的な処理の考えは筆者のものと変わらないようですが、より良い処理となっています。