GCD and LCM of Two Numbers Program in Python, C and Java

What You Will Learn

• The problem statement
• What GCD and LCM mean
• The link between GCD and LCM
• Program 1: Euclid’s algorithm
• Program 2: Checking every number
• Other ways: recursion, subtraction, math module, three numbers
• Which method is faster?
• Common mistakes, practice questions and FAQ

Problem Statement

Write a program to compute the greatest common divisor and the least common multiple of two integers.

The user enters two positive whole numbers. The program prints their GCD and their LCM. The interactive tool above accepts numbers from 1 to 1000.

What Are GCD and LCM?

Take 12 and 18 as an example.

• The common divisors of 12 and 18 are 1, 2, 3, 6. The largest one is 6, so GCD = 6.
• The number 36 is the first one that appears in both lists of multiples, so LCM = 36.

Two numbers with GCD 1, such as 17 and 5, are called co-prime. Their LCM is simply their product.

The Link Between GCD and LCM

For any two positive numbers a and b, the product of the numbers equals the product of their GCD and LCM:

a × b = GCD × LCM, so LCM = a × b ÷ GCD.

This is why every program in this post finds the GCD first. Once you have the GCD, the LCM is one line. Check it with a few pairs:

In the programs we write a // gcd * b (or a / gcd * b in C and Java) instead of a * b // gcd. The value is the same, but dividing first keeps the intermediate number small, so it is less likely to overflow an int.

Program 1: Euclid’s Algorithm

Euclid’s algorithm is more than 2,000 years old and it is still the best method. It is based on one fact: the GCD of two numbers does not change if you replace the bigger number by its remainder when divided by the smaller number.

GCD(x, y) = GCD(y, x mod y)

Repeat this until the remainder is 0. The last non-zero number is the GCD.

Logic:

• Read a and b. Copy them into x and y, so the originals stay available for the LCM.
• While y != 0: find r = x % y, then set x = y and y = r.
• When the loop ends, x is the GCD.
• Calculate lcm = a // gcd * b and print both results.

Python program

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
x = a
y = b
while y != 0:
    r = x % y
    x = y
    y = r
gcd = x
lcm = a // gcd * b
print("GCD =", gcd)
print("LCM =", lcm)

#include <stdio.h>
int main() {
    int a, b;
    printf("Enter first number: ");
    scanf("%d", &a);
    printf("Enter second number: ");
    scanf("%d", &b);
    int x = a, y = b, r;
    while (y != 0) {
        r = x % y;
        x = y;
        y = r;
    }
    int gcd = x;
    int lcm = a / gcd * b;
    printf("GCD = %d\n", gcd);
    printf("LCM = %d\n", lcm);
    return 0;
}

import java.util.Scanner;
public class GcdLcm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int a = sc.nextInt();
        System.out.print("Enter second number: ");
        int b = sc.nextInt();
        int x = a, y = b, r;
        while (y != 0) {
            r = x % y;
            x = y;
            y = r;
        }
        int gcd = x;
        int lcm = a / gcd * b;
        System.out.println("GCD = " + gcd);
        System.out.println("LCM = " + lcm);
    }
}

Sample output:

Enter first number: 12
Enter second number: 18
GCD = 6
LCM = 36

Another run:

Enter first number: 17
Enter second number: 5
GCD = 1
LCM = 85

Dry run for a = 12, b = 18:

When y becomes 0 the loop stops, and x = 6 is the GCD. Then LCM = 12 ÷ 6 × 18 = 36.

Dry run for a = 48, b = 36:

When y becomes 0 the loop stops, and x = 12 is the GCD. Then LCM = 48 ÷ 12 × 36 = 144.

Dry run for a = 17, b = 5:

When y becomes 0 the loop stops, and x = 1 is the GCD. Then LCM = 17 ÷ 1 × 5 = 85.

Why does it work? Any number that divides both x and y also divides the remainder x % y, because the remainder is x minus a whole number of copies of y. So the pair (x, y) and the pair (y, x % y) have exactly the same common divisors. The numbers get smaller every round, and the loop must end at 0.

Picture it: a rectangle 18 units long and 12 units wide can be cut into squares. First cut one 12 × 12 square, which leaves a 6 × 12 strip. That strip is cut into two 6 × 6 squares, with nothing left. The side of the biggest square that fits exactly is the GCD, here 6. The interactive tool above draws the same idea with bars and blocks.

Program 2: Checking Every Number

This method follows the definition of the GCD directly. The GCD cannot be bigger than the smaller number, so we test every i from 1 up to the smaller number. Each time i divides both numbers, we remember it. The last one remembered is the largest, so it is the GCD.

Logic:

• Find m, the smaller of a and b. Start with gcd = 1, because 1 divides everything.
• Loop i from 1 to m. If a % i == 0 and b % i == 0, set gcd = i.
• Calculate the LCM with the same formula as before.

Python program

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
m = min(a, b)
gcd = 1
for i in range(1, m + 1):
    if a % i == 0 and b % i == 0:
        gcd = i
lcm = a // gcd * b
print("GCD =", gcd)
print("LCM =", lcm)

#include <stdio.h>
int main() {
    int a, b;
    printf("Enter first number: ");
    scanf("%d", &a);
    printf("Enter second number: ");
    scanf("%d", &b);
    int m = (a < b) ? a : b;
    int gcd = 1;
    for (int i = 1; i <= m; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    int lcm = a / gcd * b;
    printf("GCD = %d\n", gcd);
    printf("LCM = %d\n", lcm);
    return 0;
}

import java.util.Scanner;
public class GcdLcm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int a = sc.nextInt();
        System.out.print("Enter second number: ");
        int b = sc.nextInt();
        int m = Math.min(a, b);
        int gcd = 1;
        for (int i = 1; i <= m; i++) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }
        int lcm = a / gcd * b;
        System.out.println("GCD = " + gcd);
        System.out.println("LCM = " + lcm);
    }
}

Sample output:

Enter first number: 12
Enter second number: 18
GCD = 6
LCM = 36

Dry run for a = 12, b = 18:

The last common divisor found is 6, so GCD = 6.

Other Ways to Write the Program

Method 3: Recursion

Euclid’s rule is recursive by nature: the GCD of x and y is the GCD of y and x % y, and when y is 0 the answer is x. That fits neatly into a function that calls itself.

Python recursive program

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
g = gcd(a, b)
lcm = a // g * b
print("GCD =", g)
print("LCM =", lcm)

#include <stdio.h>
int gcd(int x, int y) {
    if (y == 0) {
        return x;
    }
    return gcd(y, x % y);
}
int main() {
    int a, b;
    printf("Enter first number: ");
    scanf("%d", &a);
    printf("Enter second number: ");
    scanf("%d", &b);
    int g = gcd(a, b);
    int lcm = a / g * b;
    printf("GCD = %d\n", g);
    printf("LCM = %d\n", lcm);
    return 0;
}

import java.util.Scanner;
public class GcdLcm {
    static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x % y);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int a = sc.nextInt();
        System.out.print("Enter second number: ");
        int b = sc.nextInt();
        int g = gcd(a, b);
        int lcm = a / g * b;
        System.out.println("GCD = " + g);
        System.out.println("LCM = " + lcm);
    }
}

Sample output:

Enter first number: 48
Enter second number: 36
GCD = 12
LCM = 144

Method 4: Subtraction method

Older textbooks use repeated subtraction. While the two numbers are different, subtract the smaller from the bigger. When they become equal, that value is the GCD. It is easy to understand, but slow for numbers like 1000 and 1, which need 999 subtractions where Euclid needs one step.

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
x = a
y = b
while x != y:
    if x > y:
        x = x - y
    else:
        y = y - x
gcd = x
lcm = a // gcd * b
print("GCD =", gcd)
print("LCM =", lcm)

Sample output:

Enter first number: 12
Enter second number: 18
GCD = 6
LCM = 36

Method 5: Python’s math module

Python already has the functions. math.gcd exists in every Python 3 version, and math.lcm was added in Python 3.9. Use them to check your own program. In an exam, write the loop version, because the examiner wants to see the logic.

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
import math
print("GCD =", math.gcd(a, b))
print("LCM =", math.lcm(a, b))

Sample output:

Enter first number: 100
Enter second number: 75
GCD = 25
LCM = 300

Method 6: LCM without the GCD

You can also find the LCM directly. Start from the bigger number and keep adding 1 until the number is divisible by both. This works for small numbers, but the loop can run thousands of times, so the GCD formula is better.

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
lcm = max(a, b)
while lcm % a != 0 or lcm % b != 0:
    lcm = lcm + 1
print("LCM =", lcm)

Sample output:

Enter first number: 12
Enter second number: 18
LCM = 36

Method 7: Prime factorisation

This is the method taught in maths class. Break each number into prime factors. The GCD takes the common primes with the smaller power, and the LCM takes every prime with the bigger power.

• GCD = 2 × 3 = 6 (the smaller power of each common prime).
• LCM = 2² × 3² = 4 × 9 = 36 (the bigger power of each prime).

A program can print the prime factors with this helper. It is useful for checking your answer, but Euclid’s method is shorter and faster for finding the GCD.

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
def factors(n):
    f = []
    d = 2
    while n > 1:
        while n % d == 0:
            f.append(d)
            n = n // d
        d = d + 1
    return f
print(a, "=", factors(a))
print(b, "=", factors(b))

Sample output:

Enter first number: 12
Enter second number: 18
12 = [2, 2, 3]
18 = [2, 3, 3]

GCD and LCM of three numbers

Apply the function twice: GCD(a, b, c) = GCD(GCD(a, b), c), and LCM(a, b, c) = LCM(LCM(a, b), c).

import math
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
c = int(input("Enter third number: "))
g = math.gcd(math.gcd(a, b), c)
l = math.lcm(math.lcm(a, b), c)
print("GCD =", g)
print("LCM =", l)

Sample output:

Enter first number: 12
Enter second number: 18
Enter third number: 30
GCD = 6
LCM = 180

Which Method Is Faster?

Checking every number needs up to m steps, where m is the smaller number. Euclid’s algorithm needs only a handful of steps, because the numbers shrink fast. Even the worst case, two consecutive Fibonacci numbers, is small: GCD(89, 55) takes 9 rounds, GCD(610, 377) takes 13 and GCD(987, 610) takes 14.

For 1000 and 999 the loop method runs 999 times, while Euclid’s algorithm finishes in 2 rounds.

Watch the int limit. In C and Java an int stops at 2,147,483,647. The LCM of two big numbers can pass that limit even when both numbers fit, for example the LCM of 100,000 and 99,999 is 9,999,900,000. Use long long in C or long in Java for large inputs. Python has no such limit.

Common Mistakes

1. Changing a and b inside the loop. The LCM formula needs the original numbers. Work on copies x and y.
2. Starting gcd at 0 in the loop method. Then the answer stays 0 if nothing is found. Start at 1, which always divides both numbers.
3. Looping up to the bigger number. It still works, but it wastes time. Stop at the smaller number.
4. Dividing by zero. In Euclid’s method, x % y is only calculated while y is not 0, so it is safe. In your own code never calculate a % 0. Also, if you use the formula a * b / gcd with both numbers equal to 0, the GCD is 0 and the division fails.
5. Using / instead of // in Python. A single / gives a decimal such as 36.0, so the LCM prints as 36.0.
6. Forgetting the overflow. a * b can overflow an int before the division happens. Divide first: a / gcd * b.
7. Mixing up the order of the updates. You must find r first, then set x = y, then y = r. If you change x first, r uses the wrong value.

Practice Questions

1. Print all common divisors of two numbers.
2. Reduce a fraction to its lowest terms, for example 18/12 becomes 3/2. Hint: divide the top and bottom by their GCD.
3. Check whether two numbers are co-prime.
4. Find the GCD and LCM of three numbers entered by the user.
5. Find the smallest number that is divisible by all the numbers from 1 to 10 (the answer is 2520).
6. Two bells ring every 12 and 18 minutes. After how many minutes do they ring together again?

Frequently Asked Questions

What is the GCD of two numbers?

The GCD, also called HCF, is the largest number that divides both numbers exactly. For 12 and 18 the GCD is 6.

What is the LCM of two numbers?

The LCM is the smallest number that both numbers divide exactly. For 12 and 18 the LCM is 36.

How do you find the GCD in Python?

Use Euclid’s algorithm: while y is not 0, replace x by y and y by x % y. When y becomes 0, x is the GCD. You can also call math.gcd(a, b).

How do you find the LCM using the GCD?

Use the formula LCM = a × b ÷ GCD. To avoid overflow, write it as a ÷ GCD × b.

Is HCF the same as GCD?

Yes. HCF (highest common factor), GCF (greatest common factor) and GCD (greatest common divisor) are three names for the same thing.

What is the GCD of two prime numbers?

If the primes are different, the GCD is 1. If they are the same prime, the GCD is that prime.

What is the GCD if one number is 0?

GCD(a, 0) = a, because every number divides 0. The LCM is 0 by convention. The programs in this post expect positive numbers, so check for 0 first if you want to allow it.

Why does Euclid’s algorithm work?

Any number that divides x and y also divides x % y, so both pairs share the same common divisors. The numbers shrink each round and the process stops at 0.

What is the time complexity of Euclid’s algorithm?

It is O(log m), where m is the smaller number. Checking every number takes O(m).

Can the GCD be bigger than the LCM?

No. The GCD divides both numbers and the LCM is a multiple of both, so GCD ≤ smaller number ≤ larger number ≤ LCM. They are equal only when the two numbers are equal.