C# Program to Find LCM of Two Numbers

To find the LCM of two numbers in C#, use the formula LCM = (a * b) / GCD(a, b) where GCD is the greatest common divisor. You can write a program that calculates the GCD using the Euclidean algorithm and then computes the LCM.

Examples

Inputa = 4, b = 6

Output12

Inputa = 15, b = 20

Output60

Inputa = 7, b = 3

Output21

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (GCD) because the LCM is related to the GCD by the formula: LCM = (a * b) / GCD. The GCD can be found using the Euclidean algorithm, which repeatedly replaces the larger number by the remainder of dividing the larger by the smaller until the remainder is zero.

Algorithm

1

Get input numbers a and b

2

Calculate the GCD of a and b using the Euclidean algorithm

3

Calculate LCM using the formula: (a * b) / GCD

4

Return or print the LCM

Code

csharp

using System;
class Program {
    static int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    static void Main() {
        int a = 4, b = 6;
        int gcd = GCD(a, b);
        int lcm = (a * b) / gcd;
        Console.WriteLine($"LCM of {a} and {b} is {lcm}");
    }
}

Output

LCM of 4 and 6 is 12

Dry Run

Let's trace the example where a=4 and b=6 through the code

1

Start GCD calculation

a=4, b=6

2

First iteration of Euclidean algorithm

temp = 6; b = 4 % 6 = 4; a = 6

3

Second iteration

temp = 4; b = 6 % 4 = 2; a = 4

4

Third iteration

temp = 2; b = 4 % 2 = 0; a = 2

5

GCD found

b is 0, so GCD = 2

6

Calculate LCM

LCM = (4 * 6) / 2 = 12

a	b	temp	b after modulo
4	6	6	4
6	4	4	2
4	2	2	0

Why This Works

Step 1: Why find GCD first?

The LCM is related to the GCD by the formula LCM = (a * b) / GCD, so finding the GCD helps calculate the LCM efficiently.

Step 2: How Euclidean algorithm works

It repeatedly replaces the larger number by the remainder of dividing the larger by the smaller until the remainder is zero, which gives the GCD.

Step 3: Calculate LCM using the formula

After finding the GCD, multiply the two numbers and divide by the GCD to get the LCM.

Alternative Approaches

Using a loop to find LCM

csharp

using System;
class Program {
    static int LCM(int a, int b) {
        int max = Math.Max(a, b);
        int lcm = max;
        while (true) {
            if (lcm % a == 0 && lcm % b == 0) {
                return lcm;
            }
            lcm++;
        }
    }
    static void Main() {
        int a = 4, b = 6;
        Console.WriteLine($"LCM of {a} and {b} is {LCM(a, b)}");
    }
}

This method is simple but less efficient for large numbers because it checks multiples one by one.

Using recursion for GCD

csharp

using System;
class Program {
    static int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
    static void Main() {
        int a = 4, b = 6;
        int gcd = GCD(a, b);
        int lcm = (a * b) / gcd;
        Console.WriteLine($"LCM of {a} and {b} is {lcm}");
    }
}

This uses recursion for GCD calculation, which is elegant and concise.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

The Euclidean algorithm for GCD runs in O(log(min(a, b))) time because it reduces the problem size quickly with each modulo operation.

Space Complexity

The program uses constant extra space O(1) as it only stores a few variables for calculations.

Which Approach is Fastest?

Using the Euclidean algorithm for GCD and then the formula for LCM is faster than looping through multiples, especially for large numbers.

Approach	Time	Space	Best For
Euclidean algorithm + formula	O(log(min(a,b)))	O(1)	Efficient for all input sizes
Loop checking multiples	O(a*b) in worst case	O(1)	Simple but slow for large numbers
Recursive GCD + formula	O(log(min(a,b)))	O(log(min(a,b))) due to recursion stack	Elegant code, small inputs