easyDSA

How do you compute the GCD of two numbers?

Q: How do you compute the GCD of two numbers?

**Intuition.** The greatest common divisor is found by **Euclid's algorithm**: gcd(a, b) = gcd(b, a mod b) , repeating until the remainder is 0 — then the other number is the GCD. It works because any common divisor of a and b also divides a mod b . gcd(48, 18): replace with (b, a mod b) until b = 0 gcd(48, 18) <rect x="200" y="40" width="120" height="34" rx="6" fill="#8b5cf6" f

672 views

Understand the problem

Explain Euclid's algorithm.

mathgcd

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Euclid's algorithm + LCM

Run Playground

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b      # divide first to avoid overflow


# --- demo ---  (stdlib: math.gcd, math.lcm)
print(gcd(48, 18))   # 6
print(lcm(4, 6))     # 12

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you check for valid/balanced parentheses?

How do you check if a root-to-leaf path sums to a target?