36lcm
- 12
36=12*3- 18
36=18*2
Find LCM in Python
What you’ll learn
- LCM definition and the identity
gcd*lcm=a*b. - GCD-first LCM approach using Euclid.
- A brute multiple-scan alternative and live preview.
Overview
LCM is the first meeting point of two multiple sequences. Computing via gcd is usually fastest and cleanest.
Two programs
GCD-formula method and brute multiple-scan.
Live preview
Try pairs like (12,18), (0,7), (17,13).
Rigor
Handles zeros and sign normalization clearly.
Prerequisites
GCD concept, integer division, and loops.
- Euclidean algorithm with remainder.
- Basic Python functions and conditionals.
What is lcm?
LCM is the smallest common multiple of two numbers.
For 12 and 18, the first common multiple is 36.
12,18lcm=36
gcd6
Product216
gcd-lcm identity
lcm(a,b)=abs(a*b)/gcd(a,b) for nonzero values. Safer calculation: abs(a//g * b) after finding g=gcd(a,b).
12 and 18
gcd=6, so 12//6 * 18 = 36.
Intuition
216a*b
- Check
216/36 = 6 = gcd
Takeaway: gcd removes shared factors; lcm keeps enough factors to cover both numbers.
Live preview
Nonnegative integers in JavaScript safe range.
Algorithm
Goal: compute lcm(a,b) for integers.
Find gcd
Run Euclid loop on absolute values.
Compute lcm safely
If either value is zero return 0, else return abs(a // g * b).
📜 Pseudocode
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)1lcm from gcd (
lcm from gcd (12, 18)
Uses Euclid gcd then computes lcm by formula.
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}")Explanation
We divide by gcd before multiplying to keep numbers smaller during calculation.
2
Brute scan along multiples
Walk multiples of max(a,b) until one is divisible by both.
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)}")Explanation
Start at 18, then 36; 36 is the first multiple divisible by both 12 and 18.
Prime factorization
Take highest exponent of each prime across both factorizations, then multiply.
Interview: gcd-based lcm is usually expected first answer.
❓ FAQ
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.
🔄 Input / output examples
Try these pairs in either method.
| (a, b) | gcd | lcm |
|---|---|---|
(12, 18) | 6 | 36 |
(4, 6) | 2 | 12 |
(17, 13) | 1 | 221 |
(0, 9) | 9 | 0 |
Edge cases and pitfalls
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 result stays nonnegative.
⏱️ 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) |
The gcd-based method is preferred in real programs and interviews.
Summary
- Identity:
gcd(a,b) * lcm(a,b) = a * b. - Code: Euclid gcd, then
abs(a // g * b). - Watch-outs: zeros, sign normalization, and brute-scan speed.
Did you know?
For nonnegative integers a and b, gcd(a,b) * lcm(a,b) = a * b, with lcm(a,0)=0.
About the author
8 people found this page helpful