GCD of Two Numbers
Program to find Greatest Common Divisor using Euclidean algorithm
C++ GCD of Two Numbers Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
using namespace std;
int main() {
int a, b, temp;
cout << "Enter two numbers: ";
cin >> a >> b;
int originalA = a, originalB = b;
// Euclidean algorithm
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
cout << "GCD of " << originalA << " and " << originalB << " is: " << a << endl;
return 0;
}Enter two numbers: 48 18 GCD of 48 and 18 is: 6
Understanding GCD of Two Numbers
This program finds the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm. GCD is the largest positive integer that divides both numbers without leaving a remainder. The Euclidean algorithm is one of the oldest and most efficient algorithms in mathematics, dating back to ancient Greece.
---
1. What is GCD (Greatest Common Divisor)?
GCD of two numbers is the largest number that divides both of them exactly (without remainder).
Examples:
-
GCD = 6
(largest common divisor)
-
GCD = 4
GCD is used in:
---
2. Header File: #include <iostream>
#include <iostream>
Provides:
cout → for displaying outputcin → for reading input---
3. Declaring Variables
int a, b, temp;
Variable `a` and `b`:
a will eventually hold the GCDVariable `temp`:
a and b during the algorithmWhy save original values?
int originalA = a, originalB = b;
a and b will be modified---
4. Understanding the Euclidean Algorithm
The Euclidean algorithm is based on a key mathematical property:
GCD(a, b) = GCD(b, a % b)
This means:
Why this works:
d divides both a and b, it also divides a % b---
5. The Algorithm Step-by-Step
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
How it works:
Iteration 1 (a = 48, b = 18):
temp = b → temp = 18b = a % b → b = 48 % 18 = 12 (remainder when 48 ÷ 18)a = temp → a = 18a = 18, b = 12b != 0 → 12 != 0 →true
, continue
Iteration 2 (a = 18, b = 12):
temp = 12b = 18 % 12 = 6a = 12a = 12, b = 66 != 0 →true
, continue
Iteration 3 (a = 12, b = 6):
temp = 6b = 12 % 6 = 0 (12 is divisible by 6)a = 6a = 6, b = 00 != 0 →false
,
loop stops
Result:
a = 6 is the GCD ✅
---
6. Visual Representation
Finding GCD(48, 18):
48 ÷ 18 = 2 remainder 12
→ GCD(48, 18) = GCD(18, 12)
18 ÷ 12 = 1 remainder 6
→ GCD(18, 12) = GCD(12, 6)
12 ÷ 6 = 2 remainder 0
→ GCD(12, 6) = GCD(6, 0)
When second number is 0, GCD is the first number
→ GCD = 6 ✅
---
7. Why Save Original Values?
We save originalA and originalB because:
a and b are modified during the algorithma contains the GCD, but we lost the original numbersWithout saving:
With saving:
---
8. Why This Algorithm is Efficient
Naive approach (checking all divisors):
-
Time complexity: O(min(a, b))
Euclidean algorithm:
-
Time complexity: O(log(min(a, b)))
Example:
---
9. Edge Cases
Case 1: One number is 0
Case 2: Both numbers are equal
Case 3: One divides the other
Case 4: Coprime numbers (GCD = 1)
---
10. Displaying the Result
This prints:
Output:
GCD of 48 and 18 is: 6
---
Summary
Understanding the Euclidean algorithm is crucial for:
This is one of the most elegant and efficient algorithms in computer science, and mastering it opens doors to solving many mathematical programming problems.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for GCD of Two Numbers
This C++ program is part of the "Loop Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.