Understanding GCD and LCM

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two non-zero integers is the largest positive integer that divides both numbers without a remainder.

The Least Common Multiple (LCM) is the smallest positive integer divisible by both numbers.

Mathematical Relationship:

text (ISO Standard)
Copy
LCM(a, b) = (|a × b|) / GCD(a, b)

---

Euclidean Algorithm Implementation

The Euclidean algorithm is the fastest method to compute GCD using repeated modulo operations:

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>

/* Computes GCD using Euclidean Algorithm */
int computeGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/* Computes LCM using GCD */
long long computeLCM(int a, int b) {
    if (a == 0 || b == 0) return 0;
    int gcd = computeGCD(a, b);
    return ((long long)a / gcd) * b;
}

int main() {
    int num1 = 48, num2 = 18;

    int gcd = computeGCD(num1, num2);
    long long lcm = computeLCM(num1, num2);

    printf("Numbers: %d and %d\n", num1, num2);
    printf("GCD / HCF: %d\n", gcd);
    printf("LCM: %lld\n", lcm);

    return 0;
}

Sample Output

text (ISO Standard)
Copy
Numbers: 48 and 18
GCD / HCF: 6
LCM: 144

---

Complexity Analysis

• Time Complexity: $O(\log(\min(a, b)))$ — In the Euclidean algorithm, the remainder decreases by at least half every two iterations (Lamé's theorem).
• Auxiliary Space: O(1) — Iterative modulo operations require constant space.

---

Related Programs

• Test divisibility and factor logic in Prime Number Program in C.
• Review mathematical operations in C Programming Basics.