LCM of Two Numbers: flowchart, algorithm and program

This program reads two integers, a and b, and prints their LCM (least common multiple). It first finds the GCD with the Euclidean algorithm, then uses the formula lcm = a × b / gcd.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read a, b.
  3. Step 3: Set x = a, y = b.
  4. Step 4: If y != 0, go to step 5; otherwise go to step 8.
  5. Step 5: Set temp = y.
  6. Step 6: Set y = x % y.
  7. Step 7: Set x = temp. Go to step 4.
  8. Step 8: Set gcd = x.
  9. Step 9: Set lcm = a * b / gcd.
  10. Step 10: Print lcm.
  11. Step 11: Stop.

Pseudocode

BEGIN
    READ a, b
    x ← a, y ← b
    WHILE y != 0 DO
        temp ← y
        y ← x % y
        x ← temp
    END WHILE
    gcd ← x
    lcm ← a * b / gcd
    PRINT lcm
END

Program in C, Python and Java

LCM of Two Numbers program in C

#include <stdio.h>

int main() {
    int a, b, x, y, temp, gcd, lcm;

    printf("Enter a: ");
    scanf("%d", &a);
    printf("Enter b: ");
    scanf("%d", &b);

    x = a;
    y = b;
    while (y != 0) {
        temp = y;
        y = x % y;
        x = temp;
    }
    gcd = x;

    lcm = a * b / gcd;
    printf("LCM = %d\n", lcm);

    return 0;
}

LCM of Two Numbers program in Python

a = int(input("Enter a: "))
b = int(input("Enter b: "))

x = a
y = b
while y != 0:
    temp = y
    y = x % y
    x = temp
gcd = x

lcm = a * b // gcd
print("LCM =", lcm)

LCM of Two Numbers program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a, b, x, y, temp, gcd, lcm;

        System.out.print("Enter a: ");
        a = sc.nextInt();
        System.out.print("Enter b: ");
        b = sc.nextInt();

        x = a;
        y = b;
        while (y != 0) {
            temp = y;
            y = x % y;
            x = temp;
        }
        gcd = x;

        lcm = a * b / gcd;
        System.out.println("LCM = " + lcm);
    }
}

Sample input: a = 4, b = 6
Output: Enter a: Enter b: LCM = 12

How it works

  • Copy a and b into x and y, so the original values stay safe for the final formula.
  • While y is not 0, do the Euclidean step: save y in temp, set y = x % y, then set x = temp. This keeps replacing the pair with (smaller number, remainder).
  • When y becomes 0, x holds the GCD, so gcd = x. For a = 4, b = 6 the pairs go (4,6) → (6,4) → (4,2) → (2,0), so gcd = 2.
  • Apply lcm = a * b / gcd using the original a and b. Here 4 * 6 / 2 = 12, which is printed as LCM = 12.

Dry run (trace table)

StepLineBoxabxytempgcdlcmOutput
13Start
27Read a, b46
312x = a, y = b4646
413y != 0?4646
514temp = y46466
615y = x % y46446
716x = temp46646
813y != 0?46646
914temp = y46644
1015y = x % y46624
1116x = temp46424
1213y != 0?46424
1314temp = y46422
1415y = x % y46402
1516x = temp46202
1613y != 0?46202
1718gcd = x462022
1820lcm = a * b / gcd46202212
1921Print lcm46202212LCM = 12
2023Stop46202212

Time and space complexity

Time: O(log(min(a, b))) · Space: O(1). Each Euclid step shrinks the remainder at least by half every two iterations, and only a few variables are used.

Common mistakes

  • Running the Euclidean loop directly on a and b, which destroys their values, so a * b is wrong afterwards. Use the copies x and y.
  • Forgetting that a * b can overflow int for large inputs. Dividing first (a / gcd * b) is safer.
  • Entering 0 for both numbers. Then gcd is 0 and the division a * b / gcd crashes, so check for this case.

Viva questions

Q1. What is the LCM of two numbers, and how does your program compute it?

The LCM is the smallest number that both a and b divide exactly. The program first finds the GCD using Euclid's algorithm, then uses the identity LCM = a*b / GCD.

Q2. Why do you copy a and b into x and y before the loop?

The loop changes x and y until y becomes 0. I still need the original a and b on line 20 to compute a*b, so I work on copies.

Q3. Explain what lines 14 to 16 do and why temp is needed.

Each pass replaces the pair (x, y) with (y, x % y). temp holds the old y so that x can take it after y has been overwritten with the remainder; without temp the old value of y would be lost.

Q4. Why does the while loop stop when y is 0, and why is the GCD then in x?

GCD(x, 0) is x, because x divides 0 and itself. The remainder shrinks on every step until it reaches 0, and the last non-zero remainder, now stored in x, is the GCD.

Q5. Trace the program for a = 12 and b = 18.

(x, y) goes (12, 18), then (18, 12), then (12, 6), then (6, 0). The loop stops with gcd = 6, so lcm = 12*18/6 = 36.

Q6. What happens if the user enters 0 for both numbers, or for just one?

If both are 0, the loop is skipped, gcd is 0, and a*b/gcd is a division by zero, which crashes the program. If only one is 0, the gcd is the other number and the LCM prints as 0, so a check for zero input is needed.

Q7. What can go wrong with a * b on line 20, and how would you fix it?

For large inputs a*b can overflow int even when the final LCM would fit. Writing a / gcd * b, or using long long, avoids this. Dividing first is safe because gcd divides a exactly.

Q8. What is the time complexity of the loop, and what changes if the inputs are negative?

It is O(log(min(a, b))), because the remainder at least halves every two steps. With negative inputs the % result can be negative, so the gcd and the LCM may come out negative. Taking absolute values first fixes this.

Frequently asked questions

Why does lcm = a × b / gcd work?

The product a × b counts every shared prime factor twice, and the GCD is exactly the shared part. Dividing by the GCD removes the duplicate, leaving the smallest number both a and b divide into.

What is the LCM of 4 and 6, and how does the program get it?

The LCM is 12. The loop finds gcd = 2, and then 4 * 6 / 2 = 12.

Why copy a and b into x and y?

The Euclidean loop changes the values it works on. Using copies keeps a and b unchanged, so the final formula a * b / gcd still uses the original numbers.

More programs

← All programs

Try AI Flowchart free →