原文链接：http://www.cnblogs.com/lovepurple/archive/2013/04/09/3010313.html

直接上代码，算法的核心思想就是大数除小数，如果得出来的数有余数，把这个余数做为下一次的除数，上一次的除数做为被除数，直到最后相除的余数为0，则除数即为最大公约数

本算法里使用的是递归的思路。

/*  CommonDivisor 求最大公约数
 */
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace CommonDivisor
{
    class Program
    {

        static void Main(string[] args)
        {

            int firstNum, secondNum;
            Console.Write("Please input the first num:");
            firstNum = int.Parse(Console.ReadLine());
            Console.Write("Please input the second num:");
            secondNum = int.Parse(Console.ReadLine());

            int commonDivisor;

            if (firstNum > secondNum)
            {
                commonDivisor = CommonDiv(secondNum, firstNum);
            }
            else
            {
                commonDivisor = CommonDiv(firstNum, secondNum);
            }

            Console.WriteLine("{0},{1} Max Common Divisor = {2}",firstNum,secondNum,commonDivisor);

            Console.ReadKey();
        }

        #region 求出两个数的最大公约数
        /// <summary>
        /// 求出两个数的最大公约数
        /// </summary>
        /// <param name="minNum">较小的一个数</param>
        /// <param name="maxNum">较大的数</param>
        /// <returns>最大公约数</returns>
        static int CommonDiv(int minNum, int maxNum)
        {
            int common = 1;
            if (minNum == maxNum)
            {
                common = minNum;
                return common;
            }
            else
            {
                if (maxNum % minNum == 0)
                {
                    common = minNum;
                }
                else
                {
                    common = CommonDiv(maxNum % minNum,minNum);
                }
            }
            return common;
        }
    }
#endregion
}

　　

转载于:https://www.cnblogs.com/lovepurple/archive/2013/04/09/3010313.html