Click here to Skip to main content
12,503,681 members (56,535 online)
Click here to Skip to main content
Add your own
alternative version

Stats

17.7K views
3 bookmarked
Posted

Fast Greatest Common Divisor (GCD) Algorithm

, 14 Feb 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
/// /// 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);
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

jfriedman
Software Developer (Senior) ASTI Transportation Inc.
United States 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

Comments and Discussions

 
GeneralDear Julius (jfriedman): My original algorithm (the core pa... Pin
DrABELL17-Feb-11 12:17
memberDrABELL17-Feb-11 12:17 
GeneralDr. Abell, Please stop. http://www.codeproject.com/KB/reci... Pin
jfriedman17-Feb-11 11:30
memberjfriedman17-Feb-11 11:30 
GeneralHi Richard, Regarding my previous post: obviously I was tal... Pin
DrABELL17-Feb-11 2:59
memberDrABELL17-Feb-11 2:59 
GeneralRe: "You point (1) is just a re-wording of my statement ..." No... Pin
Richard Deeming21-Feb-11 10:54
memberRichard Deeming21-Feb-11 10:54 
General"some languages (e.g. VB) by default use ByRef instead of by... Pin
Richard Deeming17-Feb-11 2:33
memberRichard Deeming17-Feb-11 2:33 
GeneralHi, 1. Apparently I refer to "null" (re: "...to check if th... Pin
DrABELL15-Feb-11 5:22
memberDrABELL15-Feb-11 5:22 
GeneralDr.Abell, int is a value type which can never be null. The b... Pin
jfriedman15-Feb-11 4:03
memberjfriedman15-Feb-11 4:03 
GeneralJulius, Thanks for your comment, but I still think that simp... Pin
DrABELL15-Feb-11 2:29
memberDrABELL15-Feb-11 2:29 
General1.) You are claiming that if both numbers are equal the Eucl... Pin
jfriedman14-Feb-11 23:25
memberjfriedman14-Feb-11 23:25 
General1. There are 3 reasons given: which one you are talking abou... Pin
DrABELL14-Feb-11 18:23
memberDrABELL14-Feb-11 18:23 
GeneralI am not sure how correct your assertation is... I dont' use... Pin
jfriedman14-Feb-11 10:37
memberjfriedman14-Feb-11 10:37 
GeneralHi: I would NOT recommend the Alternate 3 for several reaso... Pin
DrABELL14-Feb-11 9:16
memberDrABELL14-Feb-11 9:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160919.1 | Last Updated 14 Feb 2011
Article Copyright 2011 by jfriedman
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid