The least common multiple (LCM) of two integers is the smallest positive number that is divisible by both.
Remember
lcm(a, b) = smallest positive m such that
m % a == 0 and m % b == 0
Identity (nonnegative a, b):
gcd(a, b) × lcm(a, b) = a × b
⇒ lcm(a, b) = |a × b| / gcd(a, b)
Example: a = 12, b = 18
Multiples of 12: 12, 24, 36, 48, …
Multiples of 18: 18, 36, 54, …
First shared = 36
Check: gcd(12, 18) = 6 → 12 × 18 / 6 = 36
a
b
gcd
lcm
12
18
6
36
7
5
1
35
0
15
15
0
Approach
How to Find LCM in C
Four clear steps — prefer the GCD formula in interviews and real code.
Take absolute values so negatives do not change the LCM.
If either value is 0, return 0.
Compute gcd(a, b) with Euclid’s algorithm.
Return |a / gcd × b| (divide before multiply to reduce overflow risk).
Method
Idea
Time
Best for
GCD formula
|a / gcd × b|
O(log min)
Interviews, production
Multiple scan
Increase by max(a, b) until both divide
O(lcm / max)
Teaching the definition
Pseudocode
Pseudocode
function Gcd(a, b):
a = abs(a), b = abs(b)
while b != 0:
t = b
b = a mod b
a = t
return a
function Lcm(a, b):
a = abs(a), b = abs(b)
if a == 0 or b == 0:
return 0
g = Gcd(a, b)
return (a / g) * b
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Meaning
Smallest positive multiple of both
Formula
lcm = |a × b| / gcd(a, b)
Safe order
Divide by gcd first, then multiply
Zero
lcm(0, n) = 0
Three numbers
lcm(lcm(a, b), c)
Classic check
lcm(12, 18) = 36
Try it
Live Preview
Enter two integers to see their GCD and LCM.
Whole numbers (absolute values used). Tap a chip or type a pair.
Result
a = 12, b = 18
gcd(12, 18) = 6
lcm = |12 × 18| / 6 = 36
Start with the GCD formula — fast and interview-ready. Use the multiple scan when you want to show the definition directly.
Example 1 — GCD Formula
Compute Euclid’s GCD, then return |a / gcd × b|.
C
#include <stdio.h>
#include <stdlib.h>
long long gcd(long long a, long long b)
{
long long t;
a = llabs(a);
b = llabs(b);
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
long long lcm(long long a, long long b)
{
a = llabs(a);
b = llabs(b);
if (a == 0 || b == 0)
{
return 0;
}
return (a / gcd(a, b)) * b;
}
int main(void)
{
printf("LCM = %lld\\n", lcm(12, 18));
return 0;
}
Output
LCM = 36
How It Works
Take absolute values with llabs so sign does not matter.
If either side is 0, return 0.
gcd repeats a % b until the remainder is 0.
For 12 and 18, gcd is 6.
(12 / 6) * 18 = 36 — divide first to keep the product smaller.
Example 2 — Multiple Scan
Start from the larger number and step by that size until both divide evenly.
C
#include <stdio.h>
#include <stdlib.h>
long long lcm(long long a, long long b)
{
long long step;
long long candidate;
a = llabs(a);
b = llabs(b);
if (a == 0 || b == 0)
{
return 0;
}
step = a > b ? a : b;
candidate = step;
while (1)
{
if (candidate % a == 0 && candidate % b == 0)
{
return candidate;
}
candidate += step;
}
}
int main(void)
{
printf("%lld\\n", lcm(12, 18)); /* 36 */
printf("%lld\\n", lcm(7, 5)); /* 35 */
return 0;
}
Output
36
35
How It Works
Handle zeros and absolute values like Example 1.
Set step = max(a, b) — the LCM cannot be smaller than that.
Test candidate; if both divide it, you found the LCM.
Otherwise add step and try again.
Clear for teaching, but slower than the GCD formula for large values.
Edge Cases & Pitfalls
Check these before calling the solution done.
Zero
lcm(0, n) = 0
Return early so you never divide by a zero GCD path incorrectly.
Overflow
Divide first
Use (a / gcd) * b with long long for larger inputs.
Negatives
Use llabs
LCM is usually reported as a nonnegative value.
Coprime
gcd = 1
Then lcm(a, b) = |a × b| — still correct.
Analysis
Time and Space Complexity
Program
Time
Extra space
GCD formula
O(log min(a, b))
O(1)
Multiple scan
O(lcm / max(a, b))
O(1)
Euclid’s GCD dominates the formula method. The scan walks multiples until it hits the LCM.
Remember
Key Takeaways
Definition: smallest positive number divisible by both inputs.
Formula:lcm = |a × b| / gcd(a, b).
Safety: divide by gcd before multiplying; use long long.
