DEV Community

Mohammed mhanna
Mohammed mhanna

Posted on

🔢 GCD & LCM

#java #beginners #programming #algorithms

Numbers hide patterns that are incredibly useful in programming, math, and real-world applications. Two of these fundamental concepts are GCD (Greatest Common Divisor) and LCM (Least Common Multiple).

Before we dive into Java, let’s understand what they are and why they matter.

🔹 1. What Are GCD & LCM?

GCD (Greatest Common Divisor): The largest number that divides two integers without leaving a remainder.
Example: GCD(12, 18) = 6

LCM (Least Common Multiple): The smallest number that is a multiple of two integers.
Example: LCM(12, 18) = 36

💡 Relationship:

LCM(a , b) × GCD(a , b) = a × b

🔹 2. Why Do We Use Them?

Simplifying fractions → Use GCD to reduce fractions to lowest terms.

Scheduling problems → LCM helps find repeating cycles or alignments.

Mathematical algorithms → Many coding challenges use GCD and LCM.

Optimizing computations → Finding GCD efficiently can reduce problem complexity.

🔹 3. Pseudo-Code:

3.1 GCD (Euclidean Algorithm):

function GCD(a, b):
    while b ≠ 0:
        temp = b
        b = a mod b
        a = temp
    return a
Enter fullscreen mode Exit fullscreen mode 
3.2 LCM Using GCD

function LCM(a, b):
    return (a * b) / GCD(a, b)
Enter fullscreen mode Exit fullscreen mode

💡 Tip: Always calculate GCD first to make LCM computation safe and efficient.

🔹 4. Java Implementation

4.1 GCD in Java

public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
Enter fullscreen mode Exit fullscreen mode

4.2 LCM in Java

public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}

4.3 Test the Methods

public static void main(String[] args) {
int num1 = 12;
int num2 = 18;

System.out.println("GCD: " + gcd(num1, num2)); // 6
System.out.println("LCM: " + lcm(num1, num2)); // 36
Enter fullscreen mode Exit fullscreen mode

}

🔹 5. Real-World Examples

Simplifying fractions: 18/24 → divide numerator and denominator by GCD(18,24)=6 → 3/4

Task scheduling: Two tasks repeat every 12 and 18 days → they align every LCM(12,18)=36 days

Coding challenges: Problems often require finding co-prime numbers or least common multiples

🎯 Key Takeaways

GCD is the largest factor, LCM is the smallest multiple.

Euclidean Algorithm is efficient and widely used.

LCM can always be derived from GCD.

These concepts are foundational for math-heavy programming and algorithms.

💬 Question:
Have you ever solved a real-world problem using GCD or LCM? Share your example!

Top comments (0)