Definition
Largest divisor
gcd(a, b) divides both; gcd = 1 means coprime.
Find GCD in C++
Overview
What You’ll Learn
The GCD of two integers is the largest positive integer that divides both. This tutorial covers Euclid’s algorithm (iterative and recursive), std::gcd, a live preview, worked C++ examples, edge cases, and complexity.
Euclid Rule
gcd(b, a%b)
Remainders shrink until b becomes 0.
Classic 48, 18
gcd = 6
Trace: 48→18→12→6→0.
std::gcd
Library
Best for real code after you can write Euclid.
Live Preview
Try a, b
Compute gcd on magnitudes in the browser.
O(log min)
Euclid steps
Worst case near consecutive Fibonacci pairs.
Introduction
The greatest common divisor gcd(a, b) is the largest positive integer that divides both a and b. Euclid’s rule gcd(a, b) = gcd(b, a % b) reduces the pair until the remainder is zero — then the leftover value is the answer.
Example: gcd(48, 18) = 6. If gcd is 1, the numbers are coprime. Also, lcm(a, b) = |a b| / gcd(a, b) for nonzero pairs.
Why it matters?
GCD underpins fraction reduction, modular inverses, Diophantine equations, and many interview number-theory warm-ups.
Key Highlights
Euclid Step
(a, b) ← (b, a % b).
Stop at 0
When b = 0, return a.
Use std::abs
Keep the result nonnegative.
gcd(0, n)
Equals |n| for n ≠ 0.
In short: replace (a, b) with (b, a % b) until b is 0; the leftover a is the gcd.
Foundation
📝 Problem & Approach
Given integers a and b, compute gcd(a, b).
c++
// gcd(48, 18) = 6
// gcd(17, 13) = 1 (coprime)
// gcd(0, 21) = 21Inputs & Outputs
| Item | Type | Description |
|---|---|---|
a, b | int | Any integers (we normalize with std::abs). |
| Return | int | Nonnegative gcd (0 for the (0, 0) convention here). |
Minimal workflow
Pseudocode
function gcd(a, b):
a = std::abs(a)
b = std::abs(b)
while b != 0:
(a, b) = (b, a mod b)
return aMethod comparison
| Method | Idea | Notes |
|---|---|---|
| Iterative Euclid | Loop with % | O(1) extra space — interview default |
| Recursive Euclid | gcd(b, a % b) | Matches the math formula closely |
| Library | std::gcd | Best for large ints / production helpers |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Normalize | a = std::abs(a); b = std::abs(b); |
| Euclid step | int t = b; b = a % b; a = t; |
| Stop | while (b != 0) then return a |
| Library | std::gcd(a, b) |
| LCM | std::llabs((long long) a / g * b) |
| Classic | gcd(48, 18) = 6 |
Compare
📋 Iterative vs Recursive vs Library
Same Euclidean math — pick by clarity and constraints.
Iterative
while (b != 0) { ... }O(1) space — best default
Recursive
gcd(b, a % b)Reads like the textbook rule
Library
std::gcdPrefer for large integers
Interview tip
write EuclidThen mention std::gcd / binary gcd
Context
When This Problem Shows Up
Reach for GCD whenever common divisors or modular structure matter.
Interview warm-ups
Classic modulo + loop problem with log-time analysis.
Fraction reduction
Divide numerator and denominator by gcd.
Modular inverses
Inverse of a mod m exists when gcd(a, m) = 1.
After Fibonacci
Worst-case Euclid pairs are consecutive Fibonacci numbers.
Define gcd(0, 0)
State the convention (often 0) before coding.
Key benefit: a short log-time algorithm that unlocks fractions, LCM, and modular arithmetic.
Interactive
🔮 Live Preview
Enter two integers (safe range). We compute gcd on magnitudes.
Hands-On
Examples Gallery
Three complete C++ programs — iterative Euclid, recursive Euclid, and std::gcd. Click View Output to reveal sample console results.
📚 Getting Started
Interview-default loop with constant extra space.
Example 1 — Iterative Euclidean Algorithm
Uses a loop to compute gcd for 48 and 18.
c++
#include <iostream>
#include <cstdlib>
int findGcd(int num1, int num2) {
num1 = std::abs(num1);
num2 = std::abs(num2);
while (num2 != 0) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
int main() {
int number1 = 48;
int number2 = 18;
int g = findGcd(number1, number2);
std::cout << "GCD of " << number1 << " and " << number2
<< " is: " << g << "\n";
return 0;
}How It Works
Each loop step keeps the gcd unchanged and reduces the second value until it becomes zero. The leftover first value is the answer.
⚡ Recursive Style
Same remainder chain, written as a recurrence.
Example 2 — Recursive Euclidean Algorithm
Base case b == 0; otherwise recurse on (b, a % b).
c++
#include <iostream>
#include <cstdlib>
int gcdRecursive(int a, int b) {
a = std::abs(a);
b = std::abs(b);
if (b == 0) {
return a;
}
return gcdRecursive(b, a % b);
}
int main() {
int number1 = 48;
int number2 = 18;
std::cout << "GCD of " << number1 << " and " << number2
<< " is: " << gcdRecursive(number1, number2) << "\n";
return 0;
}How It Works
Recursive calls follow the same remainder chain as iterative Euclid, then return the final nonzero value. Stack depth is O(log min(a, b)).
⚙️ Library Style
Use std::gcd when you do not need to reinvent Euclid.
Example 3 — std::gcd and LCM
Library gcd plus the classic LCM identity.
c++
#include <iostream>
#include <numeric>
#include <cstdlib>
int gcd(int a, int b) {
return (int) std::gcd(a, b);
}
long long lcm(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
int g = gcd(a, b);
return std::llabs((long long)a / g * b);
}
int main() {
int pairs[][2] = { { 48, 18 }, { 17, 13 }, { 0, 21 }, { -12, 18 } };
int count = sizeof(pairs) / sizeof(pairs[0]);
for (int i = 0; i < count; i++) {
int a = pairs[i][0];
int b = pairs[i][1];
std::cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b)
<< ", lcm = " << lcm(a, b) << "\n";
}
return 0;
}How It Works
Prefer std::gcd for large integers (it also handles negatives). In interviews, write Euclid yourself first, then mention the library helper and the LCM identity.
🧠 How the Algorithm Decides
1
Normalize
Set a = std::abs(a), b = std::abs(b).
Signs
2
Euclidean loop
While b != 0, replace (a, b) with (b, a % b).
Reduce
3
Stop
When b is 0, a is the gcd.
Done
=
gcd(a, b)
Largest nonnegative common divisor.
Trace
🔎 Worked Walkthrough — gcd(48, 18)
Trace the Euclidean remainder chain for the classic interview pair.
| Step | (a, b) | a % b | Next |
|---|---|---|---|
| 1 | (48, 18) | 12 | (18, 12) |
| 2 | (18, 12) | 6 | (12, 6) |
| 3 | (12, 6) | 0 | (6, 0) |
| 4 | (6, 0) | — | return 6 |
Final answer: gcd(48, 18) = 6.
Use Cases
Where GCD shows up beyond the interview prompt.
1. Interview Warm-Ups
Modulo loops with clear log-time analysis.
Example: write findGcd(a, b).
2. Fraction Reduction
Simplify p/q by dividing by gcd.
Example: 18/48 → 3/8.
3. LCM via GCD
Compute least common multiple safely.
Example: std::abs(a / g * b) with care for overflow.
4. Modular Arithmetic
Check coprimality for inverses.
Example: gcd(a, m) = 1.
5. Common Divisors
GCD is the largest shared divisor.
Example: related interview page.
6. Bézout Follow-Ups
Extended Euclid finds x, y with ax + by = gcd.
Example: mention if asked for identity.
Pro Tip: say “gcd(a, b) = gcd(b, a % b)” before coding — it proves you know the invariant.
Advantages
Why Euclid works well in interviews and classwork.
1. Tiny Code
A few lines encode a deep number-theory idea.
2. Fast
O(log min(a, b)) steps in practice.
3. Two Valid Styles
Iterative and recursive both match the math.
4. Rich Follow-Ups
LCM, extended Euclid, and binary gcd.
Pro Tip: lead with iterative Euclid; offer recursive and std::gcd as follow-ups.
Usage Tips
Small habits that keep GCD solutions interview-ready.
1. Normalize with std::abs
Keep the returned gcd nonnegative.
2. State gcd(0, 0)
Say your convention (often 0) up front.
3. Spot-Check 48, 18
Expect 6; also try (0, 21) and (17, 13).
4. Prefer Iterative in Interviews
O(1) space and no recursion-depth worry.
5. Mention LCM
Show you know |ab| / gcd when asked.
Pro Tip: worst-case Euclid step counts appear on consecutive Fibonacci inputs — a nice follow-up after the Fibonacci page.
Common Pitfalls
Mistakes that commonly break GCD solutions.
1. Skipping std::abs
Negative inputs can yield a negative-looking remainder story.
→ Normalize with
std::absfirst.2. Undefined gcd(0, 0)
Crashing or returning nonsense.
→ Document convention (often return 0).
3. Brute-Force From min Down
Looping from min(a, b) to 1 is O(min) and slow.
→ Use Euclid instead.
4. LCM Overflow Carelessness
Computing a * b before dividing in fixed-width languages.
→ In C++, divide by gcd first or use
long longto avoidintoverflow:std::llabs((long long) a / g * b).5. Forgetting gcd(0, n) = |n|
Special-casing zero incorrectly.
→ Euclid already handles it if abs is applied.
Edge Cases
Normalize signs and define behavior for gcd(0, 0) explicitly.
Zero pair
gcd(0, 0)
Many implementations return 0 by convention.
One zero
gcd(0, n)
Equals |n| for n ≠ 0.
Sign
Negative inputs
Use absolute values to keep gcd nonnegative.
Order
gcd(a, b) = gcd(b, a)
Input order does not change the answer.
Coprime
gcd = 1
Numbers share no common divisor greater than 1.
Huge ints
Big integers
Use std::gcd; cost grows with digit length.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Invariant. gcd(a, b) = gcd(b, a % b); common divisors are preserved.
- LCM. For nonzero a, b: lcm(a, b) = |a b| / gcd(a, b).
- Bézout. There exist integers x, y with ax + by = gcd(a, b).
- Worst case. Consecutive Fibonacci numbers maximize Euclid steps.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Verify classics
- (48, 18) → 6
- (17, 13) → 1
2. Match both styles
- Iterative vs recursive
- Assert identical results
3. Zero cases
- gcd(0, 21) = 21
- Decide gcd(0, 0)
4. Reduce a fraction
- 18/48 → 3/8
- Divide by gcd
Important
Notes
- Rule: gcd(a, b) = gcd(b, a % b) until b = 0.
- Code: iterative and recursive versions both match the math.
- Watch-outs: define gcd(0, 0) and normalize sign.
- Time is O(log min(a, b)); iterative uses O(1) extra space.
Quick Takeaway: keep replacing (a, b) with (b, a % b) until b is 0; the leftover a is the gcd.
Analysis
⏱️ Time and Space Complexity
| Version | Time | Extra space |
|---|---|---|
| Iterative Euclid | O(log min(a, b)) | O(1) |
| Recursive Euclid | same | O(log min(a, b)) stack |
std::gcd | same order | O(1) |
Worst-case step count appears on consecutive Fibonacci inputs.
🎉 Conclusion
GCD is the largest nonnegative common divisor. Euclid reduces (a, b) via remainders until b is 0; write it iteratively in interviews and use std::gcd for large integers.
Practice the three examples above, then continue to happy numbers for a digit-square cycle problem.
Normalize signs, define gcd(0, 0), and mention the LCM identity when asked.
Pro Tips
💡 Best Practices
✅ Do
- State Euclid’s rule first
- Normalize with std::abs
- Prefer iterative in interviews
- Define gcd(0, 0)
- Mention std::gcd and LCM
❌ Don’t
- Brute-force from min downward
- Ignore negative inputs
- Leave gcd(0, 0) undefined
- Skip the remainder invariant
- Forget coprime means gcd = 1
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about GCD
Compute gcd the interview-friendly way.
5
Core concepts 01
Rule
gcd(b, a%b)
Euclid 02
Stop
b = 0 → a
Base 03
Signs
use std::abs
Guard 04
Library
std::gcd
Ship 05
Cost
O(log min)
Analysis❓ Frequently Asked Questions
It is the largest positive integer that divides both numbers.
For n > 0, gcd(0, n) = n. Many libraries define gcd(0,0) as 0.
Repeat (a, b) <- (b, a % b) until b becomes 0. Then a is the gcd.
Yes. C++ % can follow the dividend's sign, so normalize with std::abs first for a nonnegative gcd.
Both are correct; iterative uses constant extra space.
O(log min(a,b)) Euclidean steps in the worst case.
Yes for production helpers (C++17 <numeric>). In interviews, write Euclid yourself with std::abs, then mention std::gcd.
For nonzero a and b, lcm(a,b) = |a*b| / gcd(a,b).
Did you Know? 🔊
Bézout's identity: for integers a, b not both zero, there exist integers x, y such that gcd(a,b) = a x + b y.
Continue to Happy Number
Learn how happy numbers use repeated sums of squared digits until they reach 1 or a cycle.
About the author
9 people found this page helpful