12,503,681 members (56,535 online)
Alternative Tip/Trick
alternative version

17.7K views
3 bookmarked
Posted

# Fast Greatest Common Divisor (GCD) Algorithm

, 14 Feb 2011 CPOL
 Rate this:
/// /// Find the Greatest Common Divisor /// /// Number a /// Number b /// The greatest common Divisor public static long GCD(long a, long b) ...
/// <summary>
/// Find the Greatest Common Divisor
/// </summary>
/// <param name="a">Number a</param>
/// <param name="b">Number b</param>
/// <returns>The greatest common Divisor</returns>
public static long GCD(long a, long b)
{
while (b != 0)
{
long tmp = b;
b = a % b;
a = tmp;
}

return a;
}

/// <summary>
/// Find the Least Common Multiple
/// </summary>
/// <param name="a">Number a</param>
/// <param name="b">Number b</param>
/// <returns>The least common multiple</returns>
public static long LCM(long a, long b)
{
return (a * b) / GCD(a,b);
}

## Share

 Software Developer (Senior) ASTI Transportation Inc. United States
Livin in a lonely world, caught the midnight train going anywhere... Only thing is it was a runaway train... and it ain't ever goin back...

v//

## You may also be interested in...

 Pro Pro

 First Prev Next
 Dear Julius (jfriedman): My original algorithm (the core pa... DrABELL17-Feb-11 12:17 DrABELL 17-Feb-11 12:17
 Dr. Abell, Please stop. http://www.codeproject.com/KB/reci... jfriedman17-Feb-11 11:30 jfriedman 17-Feb-11 11:30
 Hi Richard, Regarding my previous post: obviously I was tal... DrABELL17-Feb-11 2:59 DrABELL 17-Feb-11 2:59
 Re: "You point (1) is just a re-wording of my statement ..." No... Richard Deeming21-Feb-11 10:54 Richard Deeming 21-Feb-11 10:54
 "some languages (e.g. VB) by default use ByRef instead of by... Richard Deeming17-Feb-11 2:33 Richard Deeming 17-Feb-11 2:33
 Hi, 1. Apparently I refer to "null" (re: "...to check if th... DrABELL15-Feb-11 5:22 DrABELL 15-Feb-11 5:22
 Dr.Abell, int is a value type which can never be null. The b... jfriedman15-Feb-11 4:03 jfriedman 15-Feb-11 4:03
 Julius, Thanks for your comment, but I still think that simp... DrABELL15-Feb-11 2:29 DrABELL 15-Feb-11 2:29
 1.) You are claiming that if both numbers are equal the Eucl... jfriedman14-Feb-11 23:25 jfriedman 14-Feb-11 23:25
 1. There are 3 reasons given: which one you are talking abou... DrABELL14-Feb-11 18:23 DrABELL 14-Feb-11 18:23
 I am not sure how correct your assertation is... I dont' use... jfriedman14-Feb-11 10:37 jfriedman 14-Feb-11 10:37
 Hi: I would NOT recommend the Alternate 3 for several reaso... DrABELL14-Feb-11 9:16 DrABELL 14-Feb-11 9:16
 Last Visit: 31-Dec-99 18:00     Last Update: 26-Sep-16 9:00 Refresh 1