GCD, LCM & the Euclidean Algorithm
Compute divisors fast and correctly.
GCD, LCM & the Euclidean Algorithm is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Divisors Matter
So many contest problems hinge on shared factors of two numbers. The single most useful tool here is the GCD, the greatest common divisor. 🔢
What GCD Means
The GCD of two integers is the largest number that divides both with no remainder. For 12 and 18 it is 6, since 6 splits both evenly.
The Slow Way
You could test every number down from the smaller value until one divides both. It works but is far too slow for large inputs.
The Euclidean Insight
The Euclidean algorithm is the fast way. Its key idea: the GCD of a and b equals the GCD of b and the remainder of a divided by b.
The Recurrence
Repeat the swap-and-mod step until the remainder hits zero. The last nonzero value left is your answer, the GCD itself.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aCode It Yourself
A short loop keeps replacing the pair until b reaches zero. This runs in about log steps, blazing fast even for huge numbers.
def gcd(a, b):
while b:
a, b = b, a % b
return aUse the Standard Library
You rarely need to hand-roll it. Python ships math.gcd, which is correct, fast, and handles zero arguments for you.
from math import gcd
print(gcd(12, 18))From GCD to LCM
The LCM, the least common multiple, is the smallest number both values divide. It connects directly to the GCD you just computed.
The LCM Formula
Multiply the two numbers, then divide by their GCD. Always divide first to dodge overflow on very large products.
def lcm(a, b):
return a // gcd(a, b) * bGCD of a Whole List
To fold a GCD across many numbers, chain it pairwise. Python's reduce applies math.gcd left to right over the list.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Handle the Zero Case
By definition gcd(a, 0) equals a, and gcd(0, 0) is 0. Knowing this edge case keeps your loops from misbehaving on empty input.
Quick Check
Time to confirm the core Euclidean step.
Recap
You can now compute the GCD with the Euclidean algorithm in log steps, derive the LCM from it, and fold both across a list. ✅
Frequently asked questions
Is the “GCD, LCM & the Euclidean Algorithm” lesson free?
Yes — the full text of “GCD, LCM & the Euclidean Algorithm” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “GCD, LCM & the Euclidean Algorithm”?
Compute divisors fast and correctly. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “GCD, LCM & the Euclidean Algorithm” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- GCD, LCM & the Euclidean Algorithm
- Primality Testing up to sqrt(n)
- Sieve of Eratosthenes
- Prime Factorization & Divisors