快速计算最大公约数和最小公倍数的算法

快速 GCD 和 LCM 算法

以下代码片段演示了解决基本整数数学问题的编程方案，即查找

• 最大公约数，或 GCD
• 最小公倍数，或 LCM

该解决方案以 C# 4 编写的托管 .NET 代码实现，也适用于早期版本。 它可以移植到其他语言，最显着的是 VB 系列（VB/VBA/VB.NET）、Java 和 JavaScript，前提是正确处理语法差异。 另一个质因数分解和相应的素性测试算法已经在 CodeProject 之前的文章中描述过 [1]。

//============================================================================
// Author           :   Alexander Bell
// Copyright        :   2007-2011 Infosoft International Inc
// Date Created     :   01/15/2007
// Last Modified    :   01/11/2011
// Description      :   Find Greatest Common Divisor (GCD) and
//                  :   Least Common Multiple (LCM) 
//                  :   of two Int64 using Euclid algorithm
//============================================================================
// DISCLAIMER: This Application is provide on AS IS basis without any warranty
//****************************************************************************

//****************************************************************************
// TERMS OF USE     :   This module is copyrighted.
//                  :   You can use it at your sole risk provided that you keep
//                  :   the original copyright note.
//******************************************************************************
using System;

namespace Infosoft.Fractions
{
    public static partial class Integers
    {
        #region GCD of two integers
        /// <summary>
        /// find Greatest Common Divisor (GCD) of 2 integers
        /// using Euclid algorithm; ignore sign
        /// </summary>
        /// <param name="Value1">Int64</param>
        /// <param name="Value2">Int64</param>
        /// <returns>Int64: GCD, positive</returns>
        public static Int64 GCD( Int64 Value1, Int64 Value2)
        {
            Int64 a;            // local var1
            Int64 b;            // local var2
            Int64 _gcd = 1;     // Greates Common Divisor

            try
            {
                // throw exception if any value=0
                if(Value1==0 || Value2==0)   {
                    throw new ArgumentOutOfRangeException(); 
                }

                // assign absolute values to local vars
                a = Math.Abs(Value1);
                b = Math.Abs(Value2); 

                // if numbers are equal return the first
                if (a==b) {return a;}
               // if var "b" is GCD return "b"
                else if (a>b && a % b==0) {return b;}
               // if var "a" is GCD return "a"
                else if (b>a && b % a==0) {return a;}

                // Euclid algorithm to find GCD (a,b):
                // estimated maximum iterations: 
                // 5* (number of dec digits in smallest number)
                while (b != 0) {
                    _gcd = b;
                    b = a % b;
                    a = _gcd;
                }
                return _gcd;
            }
            catch { throw; }
        }
        #endregion

        #region LCM of two integers
        /// <summary>
        /// Find Least common Multiply of 2 integers
        /// using math formula: LCM(a,b)= a*(b/GCD(a,b));
        /// </summary>
        /// <param name="Value1">Int64</param>
        /// <param name="Value2">Int64</param>
        /// <returns>Int64</returns>
        public static Int64 LCM(Int64 Value1, Int64 Value2)
        {
            try
            {
                Int64 a = Math.Abs(Value1);
                Int64 b = Math.Abs(Value2);

                // perform division first to avoid potential overflow
                a = checked((Int64)(a / GCD(a, b)));
                return checked ((Int64)(a * b));
            }
            catch { throw; }
        }
        #endregion
    }
}
//***************************************************************************

请注意，checked 关键字确保算法在发生溢出时正确引发异常，从而防止函数返回未经检查的潜在错误结果。

参考文献

1. 快速质因数分解算法[^]