#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

GCD of Two Numbers in C++

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.

What is GCD (Greatest Common Divisor)?

GCD of two numbers is the largest number that divides both of them exactly (without remainder).

Examples:

• GCD of 48 and 18:
  • Divisors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
  • Divisors of 18: 1, 2, 3, 6, 9, 18
  • Common divisors: 1, 2, 3, 6

  • GCD = 6 (largest common divisor)

GCD is used in:

• Simplifying fractions (12/18 = 2/3, where GCD(12,18)=6)
• Cryptography and number theory
• Finding LCM (Least Common Multiple)
• Many mathematical algorithms

Understanding the Euclidean Algorithm

The Euclidean algorithm is based on a key mathematical property:

GCD(a, b) = GCD(b, a % b)

This means:

• The GCD of two numbers equals the GCD of the smaller number and the remainder when dividing the larger by the smaller
• We repeat this process until the remainder becomes 0
• When remainder is 0, the other number is the GCD

The Algorithm Step-by-Step

Finding GCD(48, 18):

Iteration 1 (a = 48, b = 18):

• b = 48 % 18 = 12
• Now: a = 18, b = 12

Iteration 2 (a = 18, b = 12):

• b = 18 % 12 = 6
• Now: a = 12, b = 6

Iteration 3 (a = 12, b = 6):

• b = 12 % 6 = 0
• Now: a = 6, b = 0
• Loop stops

Result: a = 6 is the GCD ✅

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)))
• Much faster for large numbers!

Summary

• Euclidean algorithm efficiently finds GCD using the property: GCD(a, b) = GCD(b, a % b)
• The algorithm repeatedly applies modulo operation until remainder is 0
• When remainder becomes 0, the other number is the GCD
• Time complexity is O(log(min(a, b))), making it very efficient
• This algorithm is fundamental in number theory and used in many applications

Understanding the Euclidean algorithm is crucial for:

• Simplifying fractions
• Finding LCM
• Solving modular arithmetic problems
• Cryptography algorithms
• Many competitive programming problems