C#求最大公约数： 欧几里得算法 vs 辗转相除法

目录

1.最大公约数

2.欧几里得算法

3.辗转相除法

1.最大公约数

        最大公约数（Greatest Common Divisor，GCD）是两个或多个整数共有的最大的能被无余地整除的数。例如，12 和 18 的最大公约数是 6。最大公约数可以通过辗转相除法、欧几里得算法（或更相减损术等方法）求解。

2.欧几里得算法

        欧几里得算法（Euclidean Algorithm）是一种用于计算两个整数的最大公约数的高效算法，基于以下原理：如果 n1 和 n2 是两个整数，且 n1 > n2，那么 n1 和 n2 的最大公约数等于 n2 和 n1%n2 的最大公约数。这个算法会不断将较大的数替换为较小的数，并将较小的数替换为两者的余数，直到较小的数为 0，此时较大的数就是两个数的最大公约数。

// 欧几里得算法（Euclidean Algorithm）实现求最大公约数
namespace _138
{
    class Program
    {
        public static float GreatestComDivisor(int n1, int n2)
        {
            int temp = Math.Max(n1, n2);//求两个数的最大值
            n2 = Math.Min(n1, n2);      //求两个数中的最小值
            n1 = temp;                  //记录临时值
            while (n2 != 0)
            {
                n1 = n1 > n2 ? n1 : n2; //使n1中的数大于n2中的数
                int m = n1 % n2;        //记录n1求余n2的结果
                n1 = n2;                //交换两个数
                n2 = m;                 //记录求余结果
            }
            return n1;
        }

        static void Main(string[] args)
        {
            ArgumentNullException.ThrowIfNull(args);

            while (true)
            {
                Console.Write("请输入第一个数：");
                int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数
                Console.Write("请输入第二个数：");
                int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数
                if (n1 * n2 != 0)                            //判断两个数中的一个是否为0
                {
                    Console.WriteLine("最大公约数:" + GreatestComDivisor(n1, n2));
                }
                else
                {
                    Console.WriteLine("这两个数不能为0。");
                }
            }
        }
    }
}
//运行结果：
/*
请输入第一个数：12
请输入第二个数：18
最大公约数:6
请输入第一个数：34
请输入第二个数：17
最大公约数:17
请输入第一个数：
 */

3.辗转相除法

        辗转相除法（也称为更相减损术）。辗转相除法是一种用于计算两个整数的最大公约数的算法，基于以下原理：如果 a 和 b 是两个整数，且 a > b，那么 a 和 b 的最大公约数等于 b 和 a % b 的最大公约数。这个算法会不断将较大的数替换为较小的数，并将较小的数替换为两者的余数，直到较小的数为 0，此时较大的数就是两个数的最大公约数。

// 用辗转相除法计算两个整数的最大公约数

namespace _138_1
{
    class Program
    {
        public static int GreatestComDivisor(int a, int b)
        {
            while (b != 0)
            {
                int remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }

        static void Main(string[] args)
        {
            ArgumentNullException.ThrowIfNull(args);

            while (true)
            {
                Console.Write("请输入第一个数：");
                int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数
                Console.Write("请输入第二个数：");
                int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数
                if (n1 * n2 != 0)                                             //判断两个数中的一个是否为0
                {
                    Console.WriteLine("最大公约数:" + GreatestComDivisor(n1, n2));
                }
                else
                {
                    Console.WriteLine("这两个数不能为0。");
                }
            }
        }
    }
}
//运行结果：
/*
请输入第一个数：12
请输入第二个数：18
最大公约数:6
请输入第一个数：34
请输入第二个数：17
最大公约数:17
请输入第一个数：
 */