Definition
Smallest multiple
LCM is the first shared multiple of a and b.
Find LCM in Python
Overview
What You’ll Learn
The least common multiple (LCM) is the smallest positive integer divisible by both inputs. This tutorial covers the gcd-lcm identity, Euclid’s helper, a brute scan, a live preview, worked Python examples, edge cases, and complexity.
Identity
gcd × lcm
gcd(a,b) * lcm(a,b) = a * b (nonnegative).
Euclid GCD
Then formula
Compute g, then abs(a // g * b).
Classic 12,18
lcm = 36
gcd=6, so 12//6 * 18 = 36.
Live Preview
Try pairs
See gcd and lcm for any safe pair.
O(log min)
Via Euclid
GCD dominates; formula is O(1) after that.
Introduction
The least common multiple of two positive integers is the smallest positive integer that is divisible by both. Example: for 12 and 18, the first shared multiple is 36.
Interviews almost always expect the gcd-based formula first. A brute multiple-scan is fine for teaching intuition, but it can be slow when the LCM is large.
Why it matters?
LCM appears in scheduling, fraction arithmetic, and any problem where you need a shared period or common cycle length.
Key Highlights
gcd × lcm = a × b
Compute LCM from Euclid’s gcd.
Divide Before Multiply
Use a // g * b, not a * b // g first.
Zero Convention
lcm(a, 0) = 0 in most APIs.
Nonnegative Result
Take absolute values so LCM stays ≥ 0.
In short: find gcd with Euclid, return 0 if either input is 0, otherwise return abs(a // g * b).
Foundation
📝 Problem & Approach
Given integers a and b, compute their least common multiple (nonnegative).
python
# 12, 18 → gcd=6 → 12//6 * 18 = 36
# 4, 6 → gcd=2 → 4//2 * 6 = 12
# 0, 9 → lcm = 0Inputs & Outputs
| Item | Type | Description |
|---|---|---|
a, b | int | Integers (absolute values used for gcd). |
| Return / print | int / text | Nonnegative LCM (0 if either input is 0). |
Minimal workflow
Pseudocode
function gcd(a, b):
while b != 0:
(a, b) = (b, a mod b)
return a
function lcm(a, b):
if a == 0 or b == 0:
return 0
g = gcd(abs(a), abs(b))
return abs((a / g) * b)Method comparison
| Method | Idea | Notes |
|---|---|---|
| gcd + formula | abs(a // g * b) | Interview default — fast |
| Brute scan | Walk multiples of max(a,b) | Clear intuition; can be slow |
| Prime factors | Max exponent per prime | Good math story; more code |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Euclid step | a, b = b, a % b |
| Safe LCM | abs(a // g * b) |
| Zero case | if a == 0 or b == 0: return 0 |
| Identity check | gcd * lcm == abs(a * b) |
| Classic pair | (12, 18) → 36 |
| Three numbers | lcm(lcm(a, b), c) |
Compare
📋 Formula vs Brute vs Factors
Three ways to get LCM — pick by speed and clarity.
gcd formula
a // g * bO(log) via Euclid — interview default
Brute scan
m += max(a,b)Easy to explain; slow when LCM is huge
Prime factors
max exponentsMatches textbook definition
Interview tip
gcd firstMention brute only as intuition
Context
When This Problem Shows Up
Reach for LCM when you need a shared multiple or period.
Interview warm-ups
Pair with GCD to show the identity.
Scheduling / cycles
Find when two repeating events next coincide.
Fraction arithmetic
Common denominators reuse LCM thinking.
After Harshad / GCD
Natural next number-theory warm-up in this chain.
Multi-argument fold
Reduce a list with pairwise LCM.
Key benefit: one short function that locks in Euclid, modular arithmetic, and a classic identity.
Interactive
🔮 Live Preview
Nonnegative integers only, within JavaScript safe range.
Hands-On
Examples Gallery
Three complete Python programs — gcd formula for 12 and 18, brute multiple-scan, and fold for three numbers. Click View Output to reveal sample console results.
📚 Getting Started
Euclid gcd plus the safe LCM formula.
Example 1 — LCM from GCD (12, 18)
Uses Euclid gcd, then computes LCM by dividing before multiplying.
python
def find_gcd(num1: int, num2: int) -> int:
num1, num2 = abs(num1), abs(num2)
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
def find_lcm(num1: int, num2: int) -> int:
if num1 == 0 or num2 == 0:
return 0
g = find_gcd(num1, num2)
return abs((num1 // g) * num2)
number1 = 12
number2 = 18
lcm = find_lcm(number1, number2)
print(f"LCM of {number1} and {number2} is: {lcm}")How It Works
Euclid finds gcd(12, 18) = 6. Then 12 // 6 * 18 = 36. Dividing first keeps the intermediate product smaller.
⚡ Brute Intuition
Walk multiples until both divide evenly.
Example 2 — Brute Scan Along Multiples
Start at max(a, b) and step by that value until both divide.
python
def lcm_scan_positive(a: int, b: int) -> int:
if a <= 0 or b <= 0:
return 0
step = max(a, b)
m = step
while m % a != 0 or m % b != 0:
m += step
return m
number1 = 12
number2 = 18
print(f"LCM of {number1} and {number2} is: {lcm_scan_positive(number1, number2)}")How It Works
Start at 18, then 36. 36 is the first multiple divisible by both 12 and 18. Prefer the gcd formula in real interviews.
⚙️ More Than Two Inputs
Fold pairwise LCM across a list.
Example 3 — LCM of Three Numbers
Reuse the same helper: lcm(lcm(a, b), c).
python
def find_gcd(a: int, b: int) -> int:
a, b = abs(a), abs(b)
while b != 0:
a, b = b, a % b
return a
def find_lcm(a: int, b: int) -> int:
if a == 0 or b == 0:
return 0
g = find_gcd(a, b)
return abs((a // g) * b)
def lcm_many(*nums: int) -> int:
result = 1
for n in nums:
result = find_lcm(result, n)
return result
print(lcm_many(4, 6, 8))
print(lcm_many(12, 18, 9))How It Works
Pairwise folding works because LCM is associative on nonnegative integers (with the zero convention). Start from 1 so the first value becomes the running LCM.
🧠 How the Algorithm Computes LCM
1
Handle zeros
If a or b is 0, return 0 immediately.
Guard
2
Find gcd
Run Euclid on absolute values.
Euclid
3
Apply formula
Return abs(a // g * b).
LCM
=
Least common multiple
Smallest shared multiple (or 0).
Trace
🔎 Worked Walkthrough — (12, 18)
Trace Euclid for gcd, then the safe LCM formula.
| Step | a | b | Action |
|---|---|---|---|
| 1 | 12 | 18 | 12, 18 = 18, 12 % 18 → (18, 12) |
| 2 | 18 | 12 | 18, 12 = 12, 18 % 12 → (12, 6) |
| 3 | 12 | 6 | 12, 6 = 6, 12 % 6 → (6, 0) |
| 4 | 6 | 0 | gcd = 6; LCM = 12 // 6 * 18 = 36 |
Check: 6 * 36 = 216 = 12 * 18.
Use Cases
Where LCM shows up beyond the interview prompt.
1. Interview Warm-Ups
Pair with GCD and the product identity.
Example: write find_lcm(a, b).
2. Scheduling
Find the next time two cycles meet.
Example: buses every 12 and 18 minutes.
3. Common Denominators
Same idea as aligning fractions.
Example: 1/4 + 1/6 needs denom 12.
4. Array / List Fold
Reduce many numbers with pairwise LCM.
Example: Example 3 above.
5. Teaching Euclid
LCM is a natural follow-up after GCD.
Example: reuse the same helper.
6. Identity Checks
Verify gcd * lcm equals |a * b|.
Example: 6 * 36 = 216.
Pro Tip: say the identity out loud, then code Euclid + a // g * b.
Advantages
Why the gcd-based approach earns interview points.
1. Fast
Euclid is logarithmic; formula is constant after that.
2. Clean Identity
One equation connects GCD and LCM.
3. Reusable Helper
Same gcd function powers many problems.
4. Safer Multiplication Order
Divide by g before multiplying b.
Pro Tip: lead with the formula; mention the brute scan only if asked how you would discover LCM without gcd.
Usage Tips
Small habits that keep LCM solutions interview-ready.
1. Write GCD First
A pure Euclid helper makes LCM almost trivial.
2. Guard Zeros
Return 0 when either argument is 0.
3. Divide Before Multiply
Prefer
a // g * bover multiplying first.4. Spot-Check 12 and 18
Expect 36 — fast sanity check.
5. Normalize Signs
Use abs so the returned LCM is nonnegative.
Pro Tip: verify with gcd * lcm == abs(a * b) on a few pairs before moving on.
Common Pitfalls
Mistakes that commonly break LCM solutions.
1. Dividing by gcd(0, 0) Paths
Skipping the zero guard before the formula.
→ Return 0 when a or b is 0.
2. Multiplying Before Dividing
a * b // gcan overflow in fixed-width languages.→ Prefer
a // g * b(still exact when g divides a).3. Relying on Brute Scan Alone
Large LCMs make repeated addition slow.
→ Use the gcd formula for production and interviews.
4. Forgetting Absolute Values
Negative inputs can yield a negative product.
→ Wrap the result (and gcd inputs) with abs.
5. Confusing GCD With LCM
Returning the gcd by mistake after Euclid.
→ Apply the formula after you have g.
Edge Cases
Handle zero and sign consistently. Brute scans can be slow for large numbers.
Zero
a == 0 or b == 0
Return 0 by standard programming convention.
Brute
Slow growth
Repeated addition can take many steps if LCM is large.
Many args
3+ numbers
Fold with lcm(lcm(a,b), c).
Sign
Negative values
Use absolute values so the result stays nonnegative.
Coprime
gcd = 1
LCM becomes |a * b| (e.g. 17 and 13 → 221).
Equal
a == b
LCM equals |a| (and gcd equals |a|).
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Identity. For nonnegative a, b: gcd(a,b) * lcm(a,b) = a * b.
- Zero. By convention in code, lcm(a, 0) = 0.
- Primes. LCM keeps the highest power of each prime across both factorizations.
- Associativity. Pairwise fold works for more than two nonnegative inputs.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Classic pairs
- (12, 18) → 36
- (4, 6) → 12; (0, 9) → 0
2. Match both styles
- Formula vs brute scan
- Assert identical results on small pairs
3. Fold a list
- LCM of [2, 3, 4, 5, 7]
- Expect 420
4. Identity check
- Assert gcd * lcm == abs(a * b)
- Great self-test without looking up answers
Important
Notes
- Identity:
gcd(a,b) * lcm(a,b) = a * b(nonnegative). - Code: Euclid gcd, then
abs(a // g * b). - Watch-outs: zeros, sign normalization, and brute-scan speed.
- GCD-based LCM is preferred in real programs and interviews.
Quick Takeaway: find gcd, then LCM is abs(a // g * b) — or 0 if either input is 0.
Analysis
⏱️ Time and Space Complexity
| Method | Time | Extra space |
|---|---|---|
| gcd + formula | O(log min(a,b)) | O(1) |
| Brute scan | O(lcm / max(a,b)) worst case | O(1) |
| Fold k numbers | O(k log M) class | O(1) |
The gcd-based method is preferred in real programs and interviews.
🎉 Conclusion
LCM is the smallest shared multiple of two integers. Compute it with Euclid’s gcd and abs(a // g * b), handle zeros, and keep the result nonnegative.
Practice the three examples above, then continue to leap year for a calendar-rules warm-up.
Remember: gcd × lcm = |a × b|, and lcm(a, 0) = 0.
Pro Tips
💡 Best Practices
✅ Do
- Implement Euclid gcd first
- Use
a // g * bafter finding g - Return 0 when either input is 0
- Test (12, 18), (4, 6), and (0, 9)
- State O(log min(a,b)) complexity
❌ Don’t
- Skip the zero guard
- Rely only on brute multiple scans
- Forget abs for negative inputs
- Return gcd by mistake
- Multiply a*b before dividing in fixed-width langs
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about LCM
Compute LCM the interview-friendly way.
5
Core concepts 01
Goal
Least multiple
Definition 02
Identity
gcd × lcm
Math 03
Euclid
Then formula
Code 04
Zero
lcm(a,0)=0
Edge 05
Cost
O(log min)
Analysis❓ Frequently Asked Questions
LCM of a and b is the smallest positive number divisible by both (for positive a and b).
For nonnegative numbers, gcd(a,b)*lcm(a,b)=a*b, so lcm can be computed using gcd.
By common programming convention, lcm(0,n)=0.
Python integers are arbitrary precision, so integer overflow is not like fixed-width C integers.
Most implementations return nonnegative lcm by using absolute values.
GCD takes O(log min(a,b)) steps, then LCM is O(1) extra arithmetic.
abs(a // g * b) keeps intermediate values smaller than computing a*b first, which matters more in fixed-width languages.
Fold pairwise: lcm(lcm(a, b), c).
Did you Know? 🔊
For nonnegative integers a and b, gcd(a,b) * lcm(a,b) = a * b, with lcm(a,0)=0.
Continue to Leap Year
Learn how to check leap years with the standard 4 / 100 / 400 rules.
About the author
8 people found this page helpful