最大公約数計算プログラム

本日の１日１題枠です。

〇お題

問題: 最大公約数 (GCD) 計算

与えられた2つの整数の最大公約数 (GCD) を計算するプログラムを作成してみてください。GCDは、2つの整数が共通で割り切れる最大の整数です。

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

ユーザーから2つの整数を入力として受け取ります。 入力された2つの整数のGCDを計算し、それを表示します。 GCDを計算するために、ユークリッドのアルゴリズムなどの適切なアルゴリズムを使用します。 この問題を解決するプログラムを作成し、異なる整数ペアに対してテストしてみてください。また、エラーハンドリングを行い、負の整数に対しても適切に対処できるように考慮することがおすすめです。

例えば10と２の入力値の最大公約数は２となり、２１と10の最大公約数は７になります。

〇筆者の回答

このプログラムでは、最大公約数とは何かを考えて組みました。

最大公約数は2つの数字の約数のうち共通する最大値を指します。

今回はまず片方の公約数を求め、2つ目数を1つ目の訳数で割り共通する訳数を求め、その最大値を出力するようにしました。

また、最初に公約数を求める際に小さい数の公約数を求めることで余計な計算を押さえています。

using System;
using System.Collections.Generic;
                    
public class Program
{
    public static void Main()
    {
        int inputA = 18;
        int inputB =60;
        int result =0 ;
        if(inputB <inputA)
        {
             result =GreatestCommonDivisor(inputB,inputA);
        }
        else
        {
            result = GreatestCommonDivisor(inputA,inputB);
        }
        
        
        Console.WriteLine(inputA+"と"+inputB+"の最大公約数は"+result);
    }
    
    public static int GreatestCommonDivisor(int inputA, int inputB)
    {
        int result = 1;
        List<int> inputADivisor = new List<int>();
        for(int i =1; i <= inputA ;i++)
        {
            if(inputA % i == 0)//iで割り切れる＝約数
            {
                 inputADivisor.Add(i);
                Console.WriteLine(i);           }
        }
        for(int j =0 ; j <= inputADivisor.Count-1 ; j++)
        {
            if(inputB % inputADivisor[j] == 0)//AとBの公約数
            {
                result = inputADivisor[j];
            }
        }
        
        return result ;
    }
}

〇ChatGPT先生の評価

提供されたコードは、最大公約数 (GCD) を計算するための基本的なアプローチを取っており、要求に従って正確な結果を生成しています。以下はコードの評価と改善点です：

評価:

GCDの計算: コードは最大公約数を計算するのに効果的な方法を使用しており、結果が正確です。

エラーハンドリング: 入力値の大小に関するエラーハンドリングが行われています。小さい数を求めることで余計な計算を避けています。

コメントと可読性: コードにコメントが付けられており、理解しやすい構造を持っています。

改善点:

コードの効率: 現在のコードでは、最大公約数を計算するために2つの数の約数をリストとして保持しています。これにより、余計なメモリを使用しています。代わりに、ユークリッドのアルゴリズムなどの方法を使用して、数学的なアプローチを選択することができます。このアプローチは、数の大きさに関係なく効率的です。

エラーメッセージ: ユーザーからの入力が負の数の場合にエラーメッセージを表示するようにしましたが、コード全体でエラーメッセージを表示することができます。また、ユーザーに入力を促すメッセージを追加することも考慮してください。

提供されたコードは、基本的なアプローチにおいて 90 点から 95 点の評価を受けるでしょう。改善点に対処することで、さらに高い点数を獲得できるでしょう。

〇ユークリッドのアルゴリズム

ユークリッドのアルゴリズムについては筆者が知らなかったので使えなかったのですが今回聞いてみました。

ユークリッドのアルゴリズムは、2つの整数の最大公約数 (GCD) を計算するための非常に効率的なアルゴリズムです。ユークリッドのアルゴリズムの基本的なアイデアは、次の通りです：

2つの整数を比較し、大きい方を小さい方で割ります。 剰余を計算します。これは小さい方の数になります。 剰余が0になるまで、大きい方の数を小さい方で置き換え、剰余を新しい小さい方の数で計算します。 剰余が0になったとき、そのときの小さい方の数が最大公約数 (GCD) です。 ユークリッドのアルゴリズムの特徴は、再帰的でなく、非常に効率的であることです。アルゴリズムの計算量は、2つの整数の大きさに対して対数的に増加します。したがって、非常に大きな整数に対しても素早く GCD を計算できます。

以下は、2つの整数 48 と 18 の最大公約数をユークリッドのアルゴリズムで計算する例です：

48 ÷ 18 = 2 余り 12 18 ÷ 12 = 1 余り 6 12 ÷ 6 = 2 余り 0 剰余が 0 になったとき、最大公約数は 6 です。ユークリッドのアルゴリズムは、このように効率的に GCD を計算することができます。

using System;

                    
public class Program
{
    public static void Main()
    {
        int inputA = 18;
        int inputB =60;
        int result =0 ;
        
        result = GreatestCommonDivisor(inputA,inputB);
        Console.WriteLine(inputA+"と"+inputB+"の最大公約数は"+result);
    }
    
    public static int GreatestCommonDivisor(int inputA, int inputB)
    {
        
        int result = 1;
        if(inputA>inputB)
        {
            int temp = inputA;//仮置き
            inputA = inputB;
            inputB = inputA;
        }
        
        result = inputB % inputA;
        
        while(inputA % result != 0 )
        {
            int tempResult = result;
            result = inputA & result;
            inputA = tempResult;
        }
        
        return result ;
    }
}

上記例を見るとより最適化されていることがわかります。