lcm(12,18) 36
- Shared
- First common multiple
Find LCM in C#
What you’ll learn
- What LCM (least common multiple) means and how to spot it from shared multiples.
- The standard C# approach: find GCD with Euclidean algorithm, then
lcm = a * b / gcd. - An overflow-safe multiply order and a brute-force alternative for small numbers.
Overview
LCM pairs naturally with GCD in interviews. Once you can compute greatest common divisor in a loop, LCM is one division away. You will also see why multiplying before dividing can overflow int — and how to fix that.
Two programs
GCD formula for 12 and 18, plus overflow-safe order.
Live preview
Type two integers and watch GCD steps plus the computed LCM.
Real uses
Add fractions with unlike denominators, sync repeating events, schedule problems.
Prerequisites
Modulo (%), integer division, while loops, and basic GCD intuition.
- Skim the GCD tutorial if Euclidean algorithm steps are new.
using System;,staticmethods,Console.WriteLine, string interpolation.
What is LCM?
The least common multiple of two integers is the smallest positive integer that both numbers divide evenly.
Multiples of 12: 12, 24, 36, 48…. Multiples of 18: 18, 36, 54…. The smallest value in both lists is 36, so lcm(12, 18) = 36.
lcm(12,18) 36
lcm(4,6) 12
GCD link a*b/gcd
LCM–GCD identity
For positive integers a and b: gcd(a,b) × lcm(a,b) = a × b. Rearranging: lcm(a,b) = (a × b) / gcd(a,b).
12 and 18gcd(12,18) = 6, so lcm = 12 × 18 / 6 = 36.
Quick examples
lcm(9,10) 90
- GCD
- 1 → product = LCM
Fractions: to add 1/12 + 1/18, use denominator lcm(12,18) = 36.
Live preview
Enter two non-zero integers. The widget runs Euclidean GCD, then applies the LCM formula.
Algorithm
Goal: compute lcm(a, b) for integers using GCD.
Normalize
Work with a = Math.Abs(a) and b = Math.Abs(b). Reject if either is 0.
Find GCD
Euclidean loop: while b != 0, set (a, b) = (b, a % b); GCD is final a.
Apply formula
Return (a / gcd) * b using the original magnitudes — divide first to reduce overflow risk.
📜 Pseudocode
Pseudocode
function gcd(a, b):
a ← absolute value of a
b ← absolute value of 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(a, b)
return (|a| / g) * |b|1
LCM via GCD (reference solution)
Matches the classic tutorial: FindGCD with Euclidean algorithm, then lcm = (num1 * num2) / gcd for 12 and 18 → 36.
c#
using System;
class Program
{
static int FindGCD(int num1, int num2)
{
num1 = Math.Abs(num1);
num2 = Math.Abs(num2);
while (num2 != 0)
{
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
static int FindLCM(int num1, int num2)
{
if (num1 == 0 || num2 == 0)
{
return 0;
}
int gcd = FindGCD(num1, num2);
return Math.Abs(num1 / gcd * num2);
}
static void Main()
{
int number1 = 12;
int number2 = 18;
int lcm = FindLCM(number1, number2);
Console.WriteLine($"LCM of {number1} and {number2} is: {lcm}");
}
}Explanation
gcd(12, 18) = 6. Then 12 / 6 * 18 = 36. Dividing 12 by GCD before multiplying by 18 keeps intermediate values smaller than 12 * 18.
return Math.Abs(num1 / gcd * num2);Overflow-aware order. Prefer (a/gcd)*b over (a*b)/gcd when using int.
2
Brute force: scan multiples
Beginner-friendly alternative — count upward from max(a,b) until you find a number divisible by both. Fine for small inputs; use GCD formula in interviews for large values.
c#
using System;
class Program
{
static int LcmBruteForce(int a, int b)
{
a = Math.Abs(a);
b = Math.Abs(b);
if (a == 0 || b == 0)
{
return 0;
}
int candidate = Math.Max(a, b);
while (candidate % a != 0 || candidate % b != 0)
{
candidate++;
}
return candidate;
}
static void Main()
{
int number1 = 12;
int number2 = 18;
Console.WriteLine($"LCM of {number1} and {number2} is: {LcmBruteForce(number1, number2)}");
}
}Explanation
Starting at 18, check 18 (not divisible by 12), then 19, then 20, … until 36 passes both tests. Simple to read, but slower as numbers grow.
Beyond the basics
long or BigInteger. When LCM itself may exceed int.MaxValue, promote to long or System.Numerics.BigInteger.
Three or more numbers. lcm(a,b,c) = lcm(lcm(a,b), c) — fold pairwise.
Interview: define LCM, walk 12/18, write GCD loop, finish with (a/gcd)*b and mention overflow.
❓ FAQ
The smallest positive integer that is divisible by both input numbers with no remainder.
36. Multiples of 12 include 12, 24, 36…; multiples of 18 include 18, 36, 54…; 36 is the smallest shared multiple.
lcm(a,b) = (a × b) / gcd(a,b) for positive a and b. Compute GCD with the Euclidean algorithm, then apply this formula.
Computing (a / gcd) * b avoids overflowing int when a * b is larger than int.MaxValue but LCM still fits.
LCM is defined for non-zero integers in most problems. If either input is 0, return 0 or handle as a special case.
Use Math.Abs on inputs so you work with magnitudes; lcm(-12, 18) = 36.
Yes for small teaching examples: count up from max(a,b) until you find a number divisible by both. GCD formula is faster for large inputs.
🔄 Input / output examples
Change number1 and number2 in Main, or read from console after validation.
| a | b | gcd(a,b) | lcm(a,b) |
|---|---|---|---|
12 | 18 | 6 | 36 |
4 | 6 | 2 | 12 |
9 | 10 | 1 | 90 |
7 | 7 | 7 | 7 |
0 | 5 | — | 0 (special) |
Edge cases and pitfalls
LCM is straightforward once GCD is correct — watch zeros, signs, and integer overflow.
Zero
lcm(a, 0)
Convention on this page: return 0. GCD of a and 0 is |a|, but LCM with zero is often defined as 0.
Overflow
(a * b) / gcd
a * b can overflow int even when LCM fits. Use (a / gcd) * b or long.
Negatives
lcm(-12, 18)
Math.Abs on inputs — LCM is positive (36).
Equal
lcm(n, n)
Returns |n| — a number is always a multiple of itself.
⏱️ Time and space complexity
| Approach | Time | Extra space |
|---|---|---|
| GCD formula | O(log min(|a|,|b|)) for GCD | O(1) |
| Brute-force multiples | O(lcm(a,b)) worst case | O(1) |
The GCD-based method is the standard efficient approach; brute force helps build intuition only for small numbers.
Summary
- Definition: LCM is the smallest positive integer divisible by both inputs.
- C#: compute GCD (Euclidean), then
(a/gcd)*bwithMath.Abs. - Pair with: GCD — together they solve fraction and scheduling problems.
Did you know?
For any two positive integers a and b, gcd(a,b) × lcm(a,b) = a × b. That identity is why interview solutions almost always compute GCD first, then derive LCM in one line.
About the author
6 people found this page helpful