36 lcm
- 12
36 = 12·3- 18
36 = 18·2
Find LCM in C
What you’ll learn
- The definition of lcm(
a,b) for nonnegative integers and thegcd · lcm = a · blink. - A gcd-first implementation with
long longto avoid multiplying inintfirst. - 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 wide product in JavaScript.
Rigor
lcm(0, ·), overflow, and dividing by gcd before the final multiply.
Prerequisites
Euclidean gcd, integer division, and long long arithmetic.
#include <stdio.h>,int main(void),printfwith%lldforlong longresults.- Optional:
<stdlib.h>llabsif 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 wide product (same identity as the C 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 in a wide type, 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. Fixes the mislabeled findGCD.c header from the old page by using this project’s tut-code-header. Uses long long and divides by gcd before the final multiply.
c
#include <stdio.h>
int find_gcd(int num1, int num2) {
while (num2 != 0) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
long long find_lcm_ll(int num1, int num2) {
int g;
if (num1 == 0 || num2 == 0) {
return 0LL;
}
g = find_gcd(num1, num2);
return (long long)num1 / g * (long long)num2;
}
int main(void) {
int number1 = 12;
int number2 = 18;
long long lcm = find_lcm_ll(number1, number2);
printf("LCM of %d and %d is: %lld\n", number1, number2, lcm);
return 0;
}Explanation
With g = 6, 12/6 = 2 and 2 · 18 = 36. This matches (12 · 18) / 6 = 216 / 6 without forming 12 * 18 in a narrow int first.
2
Brute scan along multiples
No explicit gcd function: walk multiples of max(a,b) until both divide. Same 12, 18 → 36. Slower in general but illustrates the definition.
c
#include <stdio.h>
int lcm_scan_positive(int a, int b) {
int step;
int m;
if (a <= 0 || b <= 0) {
return 0;
}
step = a > b ? a : b;
m = step;
while (m % a != 0 || m % b != 0) {
m += step;
}
return m;
}
int main(void) {
int number1 = 12;
int number2 = 18;
printf("LCM of %d and %d is: %d\n", number1, number2,
lcm_scan_positive(number1, number2));
return 0;
}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 in int can overflow before the division by gcd. Using a wider type or dividing first (as in a / g * b) avoids many practical overflows.
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 int 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 INT_MAX; use wider counters 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 positive lcm; gcd on negatives needs care with C remainder rules.
⏱️ 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
(long long)a / g * b(or return0if either input is zero). - Watch-outs:
intproduct overflow, brute scan overflow, 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