GCD and LCM

2023-02-11 C# Greatest Common Divisor GCD Least Common Multiple LCM algorithm

My son talked to me about Least Common Multiple (LCM) calculation, so I had a little refresher on how it is calculated. I remembered that long ago I used Euclid algorithm for calculation of Greatest Common Divisor (GCD), based on subtracting the numbers. As I checked the internet, I learned about a little more efficient Euclidean algorithm, especially when the difference between the numbers is great.

Here is a little C# implementation I came with testing the idea. The LCM calculation is based on plain formula that uses GCD.

/// Greatest Common Divisor - Euclidean algorithm (a, b) -> (b, a mod b)
static int GCD(int a, int b)
{
    while(a % b != 0)
    {
        int mod = a % b;
        a = b;
        b = mod;
    }
    return b;
}

/// Least Common Multiple
static int LCM(int a, int b)
{
    return Math.Abs(a) * (Math.Abs(b) / GCD(a, b));
}

And a little test code to exercise the algorithms and make sure it works as expected

var tests = new[] {
    (a: 2,  b: 4,  expectedGCD: 2, expectedLCM: 4 ),
    (a: 1,  b: 5,  expectedGCD: 1, expectedLCM: 5 ),
    (a: 3,  b: 6,  expectedGCD: 3, expectedLCM: 6 ),
    (a: 4,  b: 12, expectedGCD: 4, expectedLCM: 12 ),
    (a: 6,  b: 14, expectedGCD: 2, expectedLCM: 42 ),
    (a: 48, b: 18, expectedGCD: 6, expectedLCM: 144 ),
};

foreach(var test in tests)
{
    int gcd = GCD(test.a, test.b);
    Console.WriteLine($"GCD({test.a}, {test.b}) = {gcd} " 
        + (gcd == test.expectedGCD ? "OK" : $"Fail (should be {test.expectedGCD})"));

    int lcm = LCM(test.a, test.b);
    Console.WriteLine($"LCM({test.a}, {test.b}) = {lcm} " 
        + (lcm == test.expectedLCM ? "OK" : $"Fail (should be {test.expectedLCM})"));
}