Find GCD in C++

Beginner
⏱️ 8 min read
📚 Updated: May 2026
🎯 2 Code Examples
Euclid

What you’ll learn

  • The definition of gcd(a,b) for integers and the special case gcd(0, n) = |n|.
  • The Euclidean algorithm in an iterative form (like the reference) plus a compact recursive variant.
  • Where gcd shows up in fraction reduction, linear Diophantine problems, and modular arithmetic.

Overview

Euclid’s rule gcd(a,b) = gcd(b, a mod b) shrinks the pair at every step until the remainder hits zero. The surviving value is the gcd—fast, tiny code, and standard in interviews.

Two programs

Iterative and recursive Euclidean, both for 48 and 18.

Live preview

Two integers (safe range); shows gcd with the same recurrence as the C++ samples.

Rigor

Correct Euclidean wording, gcd(0,0) note, and C++ remainder sign awareness.

Prerequisites

Integer division and remainder (/ and %), while loops, and functions.

  • #include <iostream>, int main(), std::cout.
  • Optional: recursion depth limits if you port to huge integers with a naive recursive style.

What is gcd?

When a and b are not both zero, gcd(a,b) is the largest positive integer d such that d | a and d | b.

Among all positive linear combinations a x + b y with integers x, y, the smallest is gcd(a,b) (Bézout). Coprime pairs have gcd(a,b)=1.

48, 18 gcd = 6
Euclid gcd(a,b)=gcd(b,a%b)
LCM link |ab|/gcd

Reduction step

If b ≠ 0, any common divisor of a and b also divides a - q b for every integer q; taking q = floor(a/b) in the division algorithm yields a mod b. Hence gcd(a,b) = gcd(b, a mod b).

gcd(48, 18)

gcd(48,18) = gcd(18, 48 mod 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6.

Intuition

18×48 6
Idea
largest square tile for both sides
18/48 3/8
Reduce
divide by gcd 6

Takeaway: gcd is the last nonzero remainder in the Euclidean remainder chain.

Live preview

Nonnegative integers in JavaScript safe range (magnitudes used if you enter negatives).

Try (0, 21), (17, 13), or (48, 18).

Live result
Press “Compute gcd”.

Algorithm

Goal: compute gcd(a,b) for integers, assuming typical interview inputs fit in int.

Normalize (optional)

Replace a and b by their absolute values if you want a nonnegative gcd; handle (0,0) separately if needed.

Euclidean loop

While b ≠ 0, set (a,b) ← (b, a % b). When b == 0, return a.

📜 Pseudocode

Pseudocode
function gcd(a, b):  // assume nonnegative; define gcd(0,0) as needed
    while b != 0:
        (a, b) = (b, a mod b)
    return a
1

Iterative Euclidean algorithm

Matches the reference logic for 48 and 18. Uses find_gcd and int main().

c++
#include <iostream>

int find_gcd(int num1, int num2) {
    while (num2 != 0) {
        int temp = num2;
        num2 = num1 % num2;
        num1 = temp;
    }
    return num1;
}

int main() {
    int number1 = 48;
    int number2 = 18;
    int g;

    g = find_gcd(number1, number2);
    std::cout << "GCD of " << number1 << " and " << number2 << " is: " << g << "\n";

    return 0;
}

Explanation

Each iteration stores the old b in num1 and replaces b by a mod b. When b becomes 0, num1 holds the gcd.

2

Recursive Euclidean algorithm

Same result for the same inputs. Base case: gcd(a, 0) = a; otherwise recurse on (b, a % b).

c++
#include <iostream>

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

int main() {
    int number1 = 48;
    int number2 = 18;

    std::cout << "GCD of " << number1 << " and " << number2 << " is: "
              << gcd_recursive(number1, number2) << "\n";

    return 0;
}

Explanation

The call stack mirrors the manual remainder sequence. Depth is O(log min(|a|,|b|)) in typical cases—still fine for interview-sized integers.

Applications

Fractions. Divide numerator and denominator by gcd to reduce p/q to lowest terms.

Modular inverses. When gcd(a,m)=1, an inverse of a modulo m exists (extended Euclid finds it).

Also: Chinese remainder setup, linear Diophantine solvability (ax+by=c iff gcd(a,b)|c), and RSA key generation (coprimality checks).

Binary gcd (Stein)

For very large integers, Stein’s algorithm trades division for shifts and subtraction; for plain int, Euclidean code is already optimal in practice.

Interview: iterative Euclid is the default answer; mention extended gcd or binary gcd if the prompt goes deeper.

❓ FAQ

The greatest common divisor d of a and b is the largest positive integer that divides both a and b (when at least one is nonzero). Often written gcd(a,b) or (a,b).
For n > 0, gcd(0, n) = n because every positive divisor of n divides 0 as well. gcd(0, 0) is sometimes left undefined; many libraries return 0.
Repeatedly replace (a, b) with (b, a mod b) until b is 0. The gcd is then a—the last nonzero remainder from the previous step.
For built-in integers, C++ defines a/b truncating toward zero and a % b so that (a/b)*b + a%b == a. Euclidean gcd is cleaner if you first reduce to nonnegative magnitudes.
It avoids expensive division on some hardware by using shifts and subtraction; asymptotics are similar for word-sized integers, but it is a useful alternative for very large integers in specialized libraries.
Euclid's algorithm on L-bit inputs takes O(L) arithmetic steps in the worst case (Lamé/Fibonacci bound); each step dominates at O(1) for fixed-width int in typical C++ code.

🔄 Input / output examples

Change number1 and number2 in either program.

(a, b)gcd
(48, 18)6
(17, 13)1
(0, 21)21
(12, 18)6

Edge cases and pitfalls

The loop while (num2 != 0) assumes num2 eventually reaches zero; it always does for nonnegative inputs. With negatives, % signs can surprise you—normalize first.

Zero pair

gcd(0, 0)

The loop returns 0. Some definitions leave this undefined; document your convention in library code.

Sign

Negative inputs

Mathematical gcd is nonnegative. With the shown loop on raw negatives, verify results against your expected convention.

INT_MIN

abs hazard

Taking the absolute value of INT_MIN can overflow a signed int; use wider types or unsigned magnitude tricks when normalizing.

Order

gcd(a,b)=gcd(b,a)

The Euclidean update tolerates either order after the first step.

⏱️ Time and space complexity

VersionTimeExtra space
Iterative EuclidO(log min(a,b)) steps (worst Fibonacci pair)O(1)
Recursive EuclidsameO(log min(a,b)) stack frames

Lamé’s theorem bounds the number of division steps for inputs bounded by a fixed number of digits.

Summary

  • Rule: gcd(a,b)=gcd(b, a mod b) until b=0; answer is a.
  • Code: compact loop or one-line recursion; both match the math.
  • Watch-outs: gcd(0,0), negative remainders, and abs(INT_MIN).
Did you know?

Bézout's identity: for integers a, b not both zero, there exist integers x, y with gcd(a,b) = a x + b y. The extended Euclidean algorithm finds such coefficients while computing the gcd.

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

8 people found this page helpful

C++ Program to Display Fibonacci Series C++ Program to Check Happy Number