GCD and LCM Euclidean Algorithm in DSA C

Mental Model

GCD is the biggest number that divides two numbers without leftover. LCM is the smallest number both can fit into evenly. Euclid's method finds GCD by subtracting or dividing until one number becomes zero.

Analogy: Imagine two ropes of different lengths. To find the longest piece you can cut both ropes into equal pieces without leftover, you keep cutting the longer rope by the length of the shorter one until one rope is fully cut.

Number A: 48
Number B: 18

GCD process:
48 -> 18 -> 12 -> 6 -> 0

LCM uses GCD:
LCM = (A * B) / GCD

Dry Run Walkthrough

Input: Find GCD and LCM of 48 and 18

Goal: Calculate the greatest common divisor and least common multiple of 48 and 18 using Euclid's algorithm

Step 1: Calculate remainder of 48 divided by 18

48 % 18 = 12

Why: We replace 48 with 18 and 18 with remainder 12 to reduce the problem

Step 2: Calculate remainder of 18 divided by 12

18 % 12 = 6

Why: Continue reducing by replacing 18 with 12 and 12 with remainder 6

Step 3: Calculate remainder of 12 divided by 6

12 % 6 = 0

Why: When remainder is zero, the divisor 6 is the GCD

Step 4: Calculate LCM using formula (48 * 18) / 6

LCM = 864 / 6 = 144

Why: LCM is found by dividing product by GCD

Result:

GCD = 6
LCM = 144

Annotated Code

DSA C

#include <stdio.h>

// Function to find GCD using Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;           // store current b
        b = a % b;              // remainder replaces b
        a = temp;               // old b becomes new a
    }
    return a;                   // a is GCD when b is zero
}

// Function to find LCM using GCD
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b; // avoid overflow by dividing first
}

int main() {
    int a = 48, b = 18;
    int result_gcd = gcd(a, b);
    int result_lcm = lcm(a, b);
    printf("GCD = %d\n", result_gcd);
    printf("LCM = %d\n", result_lcm);
    return 0;
}

while (b != 0) {

repeat until remainder is zero

int temp = b;

store current divisor

b = a % b;

replace b with remainder of a divided by b

a = temp;

replace a with old b to continue process

return a;

return GCD when remainder is zero

return (a / gcd(a, b)) * b;

calculate LCM using GCD to avoid overflow

Output

GCD = 6

LCM = 144

Complexity Analysis

Time: O(log(min(a, b))) because each step reduces the problem size significantly by remainder operation

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Euclid's algorithm is much faster than checking all divisors up to min(a,b), which is O(min(a,b))

Edge Cases

One number is zero (e.g., gcd(0, 18))

GCD is the non-zero number, LCM is zero

DSA C

while (b != 0) {

Both numbers are equal (e.g., gcd(12, 12))

GCD is the number itself, LCM is the same number

DSA C

while (b != 0) {

One number is 1 (e.g., gcd(1, 18))

GCD is 1, LCM is the other number

DSA C

while (b != 0) {

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, reach for Euclid's algorithm because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Using subtraction instead of modulo can be slower and more complex
Fix: Use the modulo operator (%) to find remainder for faster convergence

Mistake: Calculating LCM as (a * b) without dividing by GCD can cause overflow
Fix: Calculate LCM as (a / gcd(a, b)) * b to reduce risk of overflow

Summary

Finds the greatest common divisor and least common multiple of two numbers using Euclid's remainder method.

Use when you need fast and reliable calculation of GCD and LCM for two integers.

The key insight is that GCD of two numbers equals the GCD of the smaller number and the remainder of the larger divided by the smaller.