Medium · Euclid's algorithm

GCD (Greatest Common Divisor)

gcd(12, 18) = 6. Euclid: gcd(a, b) = gcd(b, a mod b) until b hits zero. The oldest algorithm still in daily use.

Problem

Input: one line with two integers a b (0 ≤ a, b ≤ 10⁹, not both zero).

Output: their greatest common divisor.

Sample:

Input	Output
`12 18`	`6`
`17 5`	`1`

Your solution

Program.cs — your solution

Custom input for "Run my input"

Judging runs entirely in your browser against hidden tests. Your code is saved locally as you type. Ctrl+Enter judges.

Stuck? Hints

Hint 1 — the whole algorithm

while (b != 0) { int t = b; b = a % b; a = t; } — when it ends, a is the answer. Three lines, no recursion needed.

Hint 2 — why it works

Any number dividing both a and b also divides a mod b — so the pair (a, b) and (b, a mod b) share ALL common divisors. The second number shrinks fast: it at least halves every two rounds.

Solution (try first!)

string[] parts = Console.ReadLine().Split(' ');
int a = int.Parse(parts[0]);
int b = int.Parse(parts[1]);
while (b != 0) { int t = b; b = a % b; a = t; }
Console.WriteLine(a);

Euclid's is the gateway to number theory — LCM is one line away: a / gcd * b. Next: Prime Check.