GCD of Two Numbers: Iterative, Recursive, and Python

GCD and HCF are two names for the same calculation: the largest positive integer that divides both inputs without leaving a remainder.

The naming difference comes from disciplinary tradition. Computer science literature uses GCD (Greatest Common Divisor); Indian school mathematics uses HCF (Highest Common Factor). Placement papers and company tests use both interchangeably, so knowing both labels before the coding round starts avoids confusion when the question header says HCF but the examples use GCD notation.

What GCD and HCF Mean

Given two integers a and b, their GCD is the largest number that divides both exactly. For a = 18 and b = 24, the divisor-listing approach works as follows:

• Divisors of 18: 1, 2, 3, 6, 9, 18
• Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
• Common divisors: 1, 2, 3, 6
• GCD(18, 24) = 6

This manual listing is fine for exam scratchwork on small numbers. In code, three algorithmic approaches cover the range from “gets the job done on small inputs” to “explains the efficiency trade-off” to “one line in Python.”

Divisor-based reasoning extends naturally to adjacent problems. Finding integers with exactly 9 divisors in a range relies on the same prime-factorisation intuition that GCD exercises build. Getting GCD right first makes those problems easier to approach.

Method 1: Iterative Approach

The simplest implementation: start at min(a, b) and step down to 1. Return the first value that divides both inputs.

Algorithm Steps

• Find small = min(a, b).
• For i = small down to 1:
  • If a % i == 0 and b % i == 0, return i.
• Return 1 as the fallback (1 divides every integer).

C Code

#include <stdio.h>

int findGCD(int a, int b) {
    int small = (a < b) ? a : b;
    for (int i = small; i >= 1; i--) {
        if (a % i == 0 && b % i == 0)
            return i;
    }
    return 1;
}

int main() {
    int num1 = 18, num2 = 24;
    printf("GCD of %d and %d is: %d\n", num1, num2, findGCD(num1, num2));
    return 0;
}

For num1 = 18 and num2 = 24, the loop starts at 18 and steps down to 6, taking 13 iterations before returning the answer. The output is GCD of 18 and 24 is: 6.

Time complexity is O(min(a, b)). Space complexity is O(1). The loop becomes slow once inputs scale up: for a = 100,000 and b = 99,999, the loop needs up to 99,999 iterations to find GCD = 1. That is not workable in competitive programming, which is exactly the problem the Euclidean algorithm on Wikipedia was designed to solve.

Method 2: Euclid’s Recursive Algorithm

Euclid’s algorithm is the answer interviewers expect when they ask about GCD. It rests on one property of divisors:

• GCD(a, b) = GCD(b, a % b) for any b != 0
• Base case: when b == 0, return a

The reasoning behind this property: any common divisor of a and b also divides a % b (since a = q * b + (a % b) for some quotient q). This means the full set of common divisors is unchanged when you replace the pair (a, b) with (b, a % b). Repeating the substitution until b reaches zero leaves you with the GCD. The formal proof appears in the Euclidean algorithm article on Wikipedia.

The algorithm always terminates because a % b is strictly less than b. Each recursive call reduces the second argument, so b inevitably reaches zero. This termination argument is as old as Euclid’s Elements (circa 300 BCE), making GCD one of the oldest documented algorithms still in regular use.

Step-by-Step Trace: GCD(18, 24)

• GCD(18, 24): b = 24, not zero; compute 18 % 24 = 18; recurse to GCD(24, 18)
• GCD(24, 18): b = 18, not zero; compute 24 % 18 = 6; recurse to GCD(18, 6)
• GCD(18, 6): b = 6, not zero; compute 18 % 6 = 0; recurse to GCD(6, 0)
• GCD(6, 0): b = 0; return 6

Four recursive calls to reach the answer that took 13 iterations in the loop.

C Code

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int num1 = 18, num2 = 24;
    printf("GCD of %d and %d is: %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

Python Code

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(18, 24))  # Output: 6

The Python version replaces recursion with a while loop, keeping the same O(log min(a, b)) complexity but without growing the call stack. For very large inputs this matters: deep recursion in C can overflow the stack; the iterative form cannot.

According to Lamé’s theorem (see the Euclidean algorithm Wikipedia article), the number of steps is at most five times the digit count of the smaller input. For two 3-digit numbers, that cap is 15 steps regardless of which specific values you pick.

Method 3: Python’s math.gcd Built-in

Python 3.5 added math.gcd to the standard library. For placement coding tests that permit built-ins, a single import covers the entire problem:

import math

print(math.gcd(18, 24))   # 6
print(math.gcd(0, 15))    # 15
print(math.gcd(100, 75))  # 25

Edge cases per the Python 3 library documentation:

• math.gcd(0, 0) returns 0.
• math.gcd(0, n) returns n for any positive integer n.
• Python 3.9 extended math.gcd to accept multiple arguments and to handle negative integers, returning the absolute GCD.

For placement rounds targeting Python 3.5 through 3.8, pass only non-negative integers. In practice, problem setters nearly always guarantee positive input in the constraints, so this edge case rarely bites.

Complexity at a Glance

Method	Time	Space	When to use
Iterative loop	O(min(a, b))	O(1)	Teaching or inputs below 1,000
Euclid recursive (C/C++)	O(log min(a, b))	O(log min(a, b)) call stack	C or C++ interviews
Euclid while loop (Python)	O(log min(a, b))	O(1)	Python interviews, no built-ins
math.gcd (Python)	O(log min(a, b))	O(1)	Python tests permitting standard library

The recursive C version uses O(log min(a, b)) stack frames because each call adds one frame and the depth is bounded by the step count. The iterative Python version avoids that stack growth. For a broader look at how recursion depth affects memory cost, see space complexity of algorithms with examples.

Where GCD Appears in Placement Rounds

Placement papers rarely stop at “write a GCD function.” Three patterns come up consistently.

LCM from GCD

The identity LCM(a, b) = (a * b) / GCD(a, b) converts a potentially slow LCM loop into one O(log min(a, b)) GCD call. For a = 18 and b = 24:

• GCD(18, 24) = 6
• LCM = (18 * 24) / 6 = 432 / 6 = 72

Tests often phrase this as “find both GCD and LCM of two numbers.” Knowing this identity means one GCD implementation covers both parts of the question.

Fraction Simplification

To reduce a fraction p/q to its lowest terms, divide numerator and denominator by GCD(p, q). For 18/24: GCD = 6, so 18/24 simplifies to 3/4. This pattern appears in questions on rational-number arithmetic and fixed-point representation.

Co-prime Testing

Two numbers are co-prime when their GCD is 1. RSA key generation selects large prime factors by checking co-primality at each step, which is why GCD questions appear in the cryptography section of theory interviews. For coding rounds, the practical version is: “find all pairs in an array whose elements are co-prime.” That is an O(n squared) loop with a gcd() call inside each pair comparison, and the inner call dominates the complexity analysis.

Number-theory exercises build the same divisibility instincts. Programs like finding the sum of digits of a number are the usual placement warm-ups; GCD adds the efficiency dimension that separates a correct answer from a fast one.

The O(log min(a, b)) vs O(min(a, b)) efficiency gap (choosing Euclid’s algorithm over brute force) is the same category of trade-off reasoning that comes up when evaluating retrieval strategies and indexing pipelines in AI work. TinkerLLM is where you can take that analytical mindset into LLM applications, hands-on at ₹299.