GCD of Two Numbers in C++

GCD in C++ with Euclid: (a, b) → (b, a % b) until b is 0. GCD(48, 18) is 6.

IntermediateLoop ProgramsExample 5 of 14

gcd-of-two-numbers.cpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    int a, b, temp;
6    
7    cout << "Enter two numbers: ";
8    cin >> a >> b;
9    
10    int originalA = a, originalB = b;
11    
12    // Euclidean algorithm
13    while (b != 0) {
14        temp = b;
15        b = a % b;
16        a = temp;
17    }
18    
19    cout << "GCD of " << originalA << " and " << originalB << " is: " << a << endl;
20    
21    return 0;
22}

Output

Enter two numbers: 48 18
GCD of 48 and 18 is: 6

What's going on

GCD is the largest integer that divides both numbers. GCD(48, 18) is 6. This C++ program uses Euclid: replace (a, b) with (b, a % b) until b is 0. Then a is the GCD.

cin >> a >> b;

int originalA = a, originalB = b;

The loop overwrites a and b. Save copies for the print.

while (b != 0) {

temp = b;

b = a % b;

a = temp;

}

Walk 48 and 18:

48 % 18 = 12 → (18, 12)

18 % 12 = 6 → (12, 6)

12 % 6 = 0 → (6, 0) stop

a is 6. Print uses originalA and originalB: GCD of 48 and 18 is: 6.

If one number is 0, GCD is the other (Euclid stops immediately). Both 0 is undefined; this loop would hang or return 0 depending how you start — don't.

Order doesn't matter. GCD(18, 48) takes one extra remainder and lands on 6 too.

LCM is next: (a × b) / GCD. You need this loop first.

PreviousReverse a Number NextLCM of Two Numbers