### 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.

**GCD** and

**LCM** calculations are essential for fractions arithmetic: corresponding algorithms are implemented in the free online "

**3 Fractions Calculator**" (topping Google/Yahoo search list), available at:

**http://webinfocentral.com/MATH/Fractions.aspx**[

^].

Mobile version of the Fractions Calculator optimized for smart phones is available at [4]: you could see the image of Mobile Fraction Calculator running in iPad 2 (the picture has been taken at iPad 2 weekend in NY Apple store).

Another core Prime Factoring and corresponding Primality test algorithm has been described in the previous post on CodeProject [3]: corresponding demo is available at [2].

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.

##### Mobile Fraction Calculator on iPad 2

##### References

1.

**3 Fraction Calculator (best on Google)**[

^]

2.

Prime Factoring Calculator[

^]

3.

Fast Prime Factoring Algorithm[

^]

4.

Fraction Calculator, Mobile version[

^]