TQC+ C# 認證教學手冊

108、最大公因數計算

求最大公因數

使用輾轉相除法。

GCD(18, 24)

=> 18 % 24 = 18, 18 != 0

=> GCD(24, 18)

=> 24 % 18 = 6, 6 != 0

=> GCD(18, 6)

=> 18 % 6 = 0

=> 6 (the answer)

遞迴函數解法

static int GCD(int m, int n)
{
    if (m % n == 0) {
        return n;
    }
    return GCD(n, m % n);
}

參考程式碼

using System;

namespace CSD01
{
    class Program
    {
        static void Main(string[] args)
        {
            int input1 = 0;
            int input2 = 0;

            try
            {
                Console.Write("請輸入第一個介於1-100的整數>");
                String s = Console.ReadLine();
                input1 = int.Parse(s);

                if (!(input1 >= 1 && input1 < 100))
                {
                    throw new FormatException();
                }

                Console.Write("請輸入第二個介於1-100的整數>");
                s = Console.ReadLine();
                input2 = int.Parse(s);

                if (!(input2 >= 1 && input2 < 100))
                {
                    throw new FormatException();
                }

                int result = findCommon(input1, input2);

                Console.WriteLine("{0}和{1}的最大公因數是{2}", input1, input2, result);
            }
            catch (FormatException)
            {
                Console.WriteLine("輸入錯誤,請重新執行");
            }

            Console.ReadLine();
        }

        // m = 34, n = 10
        // 34 % 10 = 4
        // m = 10, n = 4
        // 10 % 4 = 2
        // m = 4, n = 2
        // 4 % 2 = 0
        // m = 2, n = 0
        // => 2
        //static int findCommon(int m, int n)
        //{
        //    if (n == 0) return m;
        //    return findCommon(n, m % n);
        //}

        static int findCommon(int m, int n)
        {
            while (m % n != 0)
            {
                int t = n;
                n = m % n;
                m = t;
            }
            return n;
        }
    }
}