36 lcm
- 12
36 = 12·3- 18
36 = 18·2
Find LCM in JavaScript
What you’ll learn
- The definition of lcm(
a,b) for nonnegative integers and thegcd · lcm = a · blink. - A gcd-first implementation that divides by
gcdbefore multiplying to reduce overflow risk inNumber. - A brute multiple scan (same
12,18→36) and a live preview.
Overview
The lcm is the smallest common multiple of two integers. Computing it via gcd is standard, fast, and easy to justify algebraically.
Two programs
Gcd formula and a stepping lcm for 12 and 18.
Live preview
Nonnegative safe integers; uses gcd and divide-before-multiply.
Rigor
lcm(0, ·), overflow, and dividing by gcd before the final multiply.
Prerequisites
Euclidean gcd, integer division, and JavaScript Number safe integers.
console.log,Number.isSafeInteger, remainder%.- Optional:
Math.absif you normalize signed inputs.
What is lcm?
For positive integers a and b, lcm(a,b) is the smallest positive integer m with a | m and b | m.
Multiples of 12 include 12, 24, 36, …; multiples of 18 include 18, 36, …. The first common positive multiple is 36 (the reference answer).
12, 18 lcm = 36
gcd 6
Product 12·18 = 216
gcd–lcm identity
For nonnegative a, b, gcd(a,b) · lcm(a,b) = a · b. Equivalently lcm(a,b) = a / gcd(a,b) · b when gcd(a,b) > 0.
12 and 18gcd(12,18)=6, so lcm = 12/6 · 18 = 2 · 18 = 36.
Intuition
216 a·b
- Check
216 / 36 = 6 = gcd
Takeaway: lcm sits at the intersection of the two multiple ladders; gcd measures overlap in prime factors.
Live preview
Nonnegative integers in the JavaScript safe range. Uses gcd then (a/g)·b (same identity as the examples).
Algorithm
Goal: compute lcm(a,b) for nonnegative integers.
gcd
Use Euclid: gcd(a,b) = gcd(b, a mod b) until the second argument is 0.
Divide before multiply
Return (a / g) * b, or 0 if either input is 0.
📜 Pseudocode
Pseudocode
function gcd(a, b): // nonnegative
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(a, b)
return (a / g) * b1lcm from gcd (
lcm from gcd (12, 18)
Same numbers and output as the reference. Uses Euclid findGcd, divides by gcd before the final multiply, and guards lcm(0, ·).
JavaScript
function findGcd(num1, num2) {
while (num2 !== 0) {
const temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
function findLcm(num1, num2) {
if (num1 === 0 || num2 === 0) {
return 0;
}
const g = findGcd(num1, num2);
return (num1 / g) * num2;
}
const number1 = 12;
const number2 = 18;
const lcmVal = findLcm(number1, number2);
console.log(
"LCM of " + number1 + " and " + number2 + " is: " + lcmVal
);Explanation
With g = 6, 12/6 = 2 and 2 · 18 = 36. This matches (12 · 18) / 6 = 216 / 6 without forming 12 * 18 first when unnecessary.
2
Brute scan along multiples
No explicit gcd call in the scan itself: walk multiples of max(a,b) until both divide. Same 12, 18 → 36. Slower in general but illustrates the definition.
JavaScript
function lcmScanPositive(a, b) {
if (a <= 0 || b <= 0) {
return 0;
}
const step = a > b ? a : b;
let m = step;
while (m % a !== 0 || m % b !== 0) {
m += step;
}
return m;
}
const number1 = 12;
const number2 = 18;
console.log(
"LCM of " +
number1 +
" and " +
number2 +
" is: " +
lcmScanPositive(number1, number2)
);Explanation
Start at 18; it is not a multiple of 12. Add another 18 to reach 36, which both divide.
Prime factorization
Factor both numbers, take the maximum exponent per prime, multiply back—useful when you already have factor tables.
Interview: prefer gcd-based lcm; mention overflow and the lcm(0, ·) convention.
❓ FAQ
The least common multiple of a and b is the smallest positive integer m such that a|m and b|m (when a and b are nonzero). It is unique for positive inputs.
For nonnegative a and b, gcd(a,b) * lcm(a,b) = a * b. Hence lcm(a,b) = a / gcd(a,b) * b, dividing before multiplying to reduce overflow risk.
Conventionally lcm(0, n) = 0 for any n, because every integer divides 0; the smallest positive multiple interpretation does not apply when one argument is 0.
Computing a * b first can exceed Number.MAX_SAFE_INTEGER even when lcm fits. Computing (a / gcd(a,b)) * b reduces the risk when intermediate values stay in the safe range.
Definitions vary on signs; this page keeps inputs nonnegative so lcm is nonnegative.
Euclid gcd costs O(log min(a,b)) steps; lcm from gcd is O(1) after that. The brute scan can be O(lcm) steps in the worst case and is mainly pedagogical.
🔄 Input / output examples
Change number1 and number2 in either program.
| (a, b) | gcd | lcm |
|---|---|---|
(12, 18) | 6 | 36 |
(4, 6) | 2 | 12 |
(17, 13) | 1 | 221 |
(0, 9) | 9 | 0 |
Edge cases and pitfalls
The naive (a * b) / gcd in a narrow type can overflow even when the true lcm fits; dividing first helps but does not remove all overflow cases for huge inputs.
Zero
a === 0 or b === 0
This page returns 0 for lcm; gcd-based code must avoid dividing by 0.
Brute
Scan overflow
Repeatedly adding step can exceed Number.MAX_SAFE_INTEGER; use gcd-based lcm or BigInt for large inputs.
Three+
More arguments
Fold: lcm(a,b,c) = lcm(lcm(a,b), c) (watch zeros at each step).
Sign
Negative inputs
Normalize with absolute values if your API promises a nonnegative lcm; ES remainder follows truncated division.
⏱️ Time and space complexity
| Method | Time | Extra space |
|---|---|---|
| gcd + formula | O(log min(a,b)) | O(1) |
| Brute scan | O(lcm / max(a,b)) steps worst case | O(1) |
The gcd-based method dominates in practice.
Summary
- Identity:
gcd(a,b) · lcm(a,b) = a · bfor nonnegativea, b. - Code: Euclid gcd, then
(a / g) * b(or return0if either input is zero). - Watch-outs: product overflow, brute scan growth, and lcm with a zero argument.
Did you know?
For nonnegative integers a and b, gcd(a,b) · lcm(a,b) = a · b (with the convention lcm(a,0)=lcm(0,b)=0). That identity is why one small gcd loop unlocks lcm.
About the author
8 people found this page helpful