12,956,197 members (101,871 online)
Tip/Trick
alternative version

#### Stats

32.1K views
13 bookmarked
Posted 24 Feb 2011

# Fast Integer Algorithms: Greatest Common Divisor and Least Common Multiple, .NET solution

, 19 Apr 2011 CPOL
 Rate this:
.NET/C# managed code implementation of 2 core algorithms of integer arithmetic: GCD and LCM (used in "3 Fraction Calculator", best on Google)

### 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].
```//============================================================================
// Author           :   Alexander Bell
// Copyright        :   2007-2011 Infosoft International Inc
// Date Created     :   01/15/2007
// 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
//****************************************************************************

//****************************************************************************
//                  :   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
}
}
//***************************************************************************```

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. 3 Fraction Calculator (best on Google)[^]
2. Prime Factoring Calculator[^]
3. Fast Prime Factoring Algorithm[^]
4. Fraction Calculator, Mobile version[^]

## Share

 President Infosoft International Inc United States
Dr. Alexander Bell is a seasoned full-stack Software Engineer (Win/Web/Mobile). He holds PhD in EE/IT, authored 37 inventions and published 300+ technical articles. Currently focused on HTML5/CSS3, Javascript, .NET/WPF/C#, Angular.js, SQL, 'Big Data', Machine Learning, AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Portfolio samples:

## You may also be interested in...

 Pro Pro

 First Prev Next
 My vote of 2 carga16-Dec-13 4:09 carga 16-Dec-13 4:09
 any of two = 0... Andrei Zakharevich1-Nov-13 6:40 Andrei Zakharevich 1-Nov-13 6:40
 Re: My vote of 5 DrABELL7-Aug-13 10:09 DrABELL 7-Aug-13 10:09
 Thanks, Hayk! Best rgds, Alex DrABELL3-Mar-11 3:35 DrABELL 3-Mar-11 3:35
 Reason for my vote of 2 This is the known algorithm of Eucli... Hayk Aleksanyan28-Feb-11 18:25 Hayk Aleksanyan 28-Feb-11 18:25
 Re: Hayk, The solution clearly states that it is using a Euclid ... DrABELL1-Mar-11 2:05 DrABELL 1-Mar-11 2:05
 Re: Hayk, I would appreciate if you could re-consider your vote ... DrABELL2-Mar-11 3:45 DrABELL 2-Mar-11 3:45
 may want to fix your formatting though :) jfriedman25-Feb-11 8:41 jfriedman 25-Feb-11 8:41
 Reason for my vote of 3 Cleaner than last time... jfriedman25-Feb-11 2:32 jfriedman 25-Feb-11 2:32
 Re: You should seriously re-consider your voting practice DrABELL8-Mar-11 1:06 DrABELL 8-Mar-11 1:06
 Last Visit: 31-Dec-99 18:00     Last Update: 29-May-17 8:50 Refresh 1