### Fast GCD and LCM algorithms

The following code snippets demonstrate the programmatic solution to the fundamental integer-math problems of finding:

**Greatest Common Divisor, or GCD** **Least Common Multiple, or LCM**

The solution is implemented as managed .NET code written in C# 4, applicable to the previous versions as well. It is portable to other languages, most notably, to the VB family (VB/VBA/VB.NET), Java and JavaScript as well, provided that the syntax differences are properly addressed. Another Prime Factoring and corresponding Primality test algorithm has been described in the previous post on CodeProject [1].

using System;
namespace Infosoft.Fractions
{
public static partial class Integers
{
#region GCD of two integers
public static Int64 GCD( Int64 Value1, Int64 Value2)
{
Int64 a;
Int64 b;
Int64 _gcd = 1;
try
{
if(Value1==0 || Value2==0) {
throw new ArgumentOutOfRangeException();
}
a = Math.Abs(Value1);
b = Math.Abs(Value2);
if (a==b) {return a;}
else if (a>b && a % b==0) {return b;}
else if (b>a && b % a==0) {return a;}
while (b != 0) {
_gcd = b;
b = a % b;
a = _gcd;
}
return _gcd;
}
catch { throw; }
}
#endregion
#region LCM of two integers
public static Int64 LCM(Int64 Value1, Int64 Value2)
{
try
{
Int64 a = Math.Abs(Value1);
Int64 b = Math.Abs(Value2);
a = checked((Int64)(a / GCD(a, b)));
return checked ((Int64)(a * b));
}
catch { throw; }
}
#endregion
}
}

Notice that `checked`

keyword ensures that the algorithm properly raises the exception in case of overflow, so preventing the potentially erroneous results being unchecked and returned by function.

**References**

1. Fast Prime Factoring Algorithm[^]