GCD Using a While Loop

Medium ⏱ 12 min 55% acceptance ★★★★★ 4.8
Write a function gcd(a, b) that computes the greatest common divisor of two positive integers using the Euclidean algorithm implemented with a while loop (no math.gcd).

Examples

Example 1
Input
gcd(48, 18)
Output
6
Explanation

Euclidean algorithm reduces (48,18) -> (18,12) -> (12,6) -> (6,0).

Example 2
Input
gcd(7, 13)
Output
1
Explanation

Coprime numbers have gcd 1.

Constraints

  • a and b are positive integers.
  • Must not use math.gcd.

Topics

Loopswhile loop

Companies

IntelCisco

Hints

Hint 1

Repeatedly replace (a, b) with (b, a % b) until b becomes 0.

Hint 2

The answer is whatever a holds once the loop ends.

← Sum of Even and Odd Numbers Separately Print a Diamond Pattern With Nested Loops →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.