Medium · algorithms

Greatest Common Divisor

Read two positive integers and print their GCD. The naive way (try every divisor) works; Euclid's way (2300 years old) is the first truly clever algorithm most people ever write.

At a glanceEuclid's algorithm — while b is not 0, replace (a, b) with (b, a % b); the answer is a, and it takes O(log min(a, b)) steps even at 10⁹.

Problem

Input: one line with two positive integers a and b (1 ≤ a, b ≤ 10⁹).

Output: their greatest common divisor.

Samples:

Input	Output
`12 18`	`6`
`7 13`	`1`

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — the key identity

Any number that divides both a and b also divides a % b — so gcd(a, b) = gcd(b, a % b). Each step shrinks the numbers, and a % b is always less than b, so it terminates fast.

Hint 2 — the loop shape

while (b != 0) { int t = a % b; a = b; b = t; } — you need the temporary t because overwriting a first would destroy the value you're about to put in b. (This is exactly the swap pattern's three-line dance.) When b hits 0, a holds the answer.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    cout << a << endl;
    return 0;
}

Why this beats the naive approach: for inputs up to a billion, trying every divisor is up to a billion iterations; Euclid takes at most ~45 (the worst case is consecutive Fibonacci numbers — see the next problem). Trace gcd(12, 18) by hand: (12,18) → (18,12) → (12,6) → (6,0) → answer 6. Once it clicks, LCM is one line away: a * b / gcd.

Deep dive

Why this works

Euclid's identity — gcd(a,b) = gcd(b, a % b) — is the oldest non-trivial algorithm still in daily use, and the model for 'shrink the problem every step'.

The cost

O(log min(a,b)). Consecutive Fibonacci numbers are the worst case.

Where it goes wrong

while (b > 0) misbehaves on negative input; normalise with abs first.
Trying every divisor from min(a,b) downwards is O(n) and times out on large coprime pairs.

Next step

Recursion that shrinks the same way: Fibonacci.

Two things to remember

gcd(a,b) = gcd(b, a % b).
O(log n), not O(n): the naive loop is a thousand times slower.

🐞 This version fails — open it and try

Prints b, which the loop left at 0

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    while (b > 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    cout << b << endl;
    return 0;
}