Problem link ও উৎস
- **Original source:** Classic exercise (related: Project Euler 5 — Smallest multiple)
- **Platform:** Project Euler —
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Easy
- **Pattern:** lcm = a // gcd(a, b) * b
- **Basic idea inherited from:** 018 — GCD using Euclidean Algorithm
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো ধনাত্মক integer `a` আর `b` দেওয়া আছে। বের করতে হবে এদের **LCM** — least common multiple (লসাগু, লঘিষ্ঠ সাধারণ গুণিতক)। মানে এমন সবচেয়ে ছোট ধনাত্মক সংখ্যা যেটা `a`-রও multiple, `b`-রও।
উদাহরণ: lcm(12, 18) = 36, কারণ 36 = 12×3 আর 36 = 18×2 — দুজনেরই গুণিতক, আর এর চেয়ে ছোট কোনো সংখ্যা দুজনেরই গুণিতক নয়।
দৈনন্দিন কাজে এটা বারবার লাগে: দুটো ঘটনা যদি আলাদা আলাদা সময় পরপর ঘটে, তারা আবার একসাথে কখন ঘটবে — সেটাই LCM।
### Input ও output {#6-example-input-and-output}
```text
a , b -> lcm
----------------------
12 , 18 -> 36
4 , 6 -> 12
5 , 7 -> 35 (coprime: lcm = a × b)
6 , 12 -> 12 (একজন অন্যজনের multiple)
10 , 10 -> 10 (একই সংখ্যা)
7 , 1 -> 7 (1-এর সাথে lcm = অন্য সংখ্যাটাই)
```
দুটো জিনিস খেয়াল করো: a, b coprime হলে (gcd = 1) lcm ঠিক `a × b` (যেমন 5, 7 → 35)। আর একজন অন্যজনের multiple হলে lcm হলো বড় সংখ্যাটাই (6, 12 → 12)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুটো বাস স্টপ থেকে ছাড়ে — একটা প্রতি 12 মিনিটে, আরেকটা প্রতি 18 মিনিটে। দুটো বাসই যদি এইমাত্র একসাথে ছেড়ে থাকে, তাহলে আবার ঠিক **একসাথে** কখন ছাড়বে?
প্রথম বাস ছাড়ে 12, 24, 36, 48... মিনিটে। দ্বিতীয়টা 18, 36, 54... মিনিটে। প্রথম যে সময়ে দুটোই মেলে — **36 মিনিট**। এটাই lcm(12, 18)।
খেয়াল করো — তুমি 36 খুঁজতে দুটো তালিকা মেলাতে পারতে, কিন্তু সেটা ধীর। GCD জানলে শর্টকাট: `12 × 18 / gcd(12,18) = 216 / 6 = 36`। দুই বাস কখন আবার মিলবে — এক ভাগেই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **018 (GCD using Euclidean Algorithm)**-এর উপর দাঁড়িয়ে। LCM-এর পুরো হিসাবটাই GCD-র উপর ভর করে — `lcm = a // gcd(a, b) * b`। GCD না জানলে LCM বের করা অনেক কঠিন (সব multiple ঘুরে দেখতে হতো)।
তাই LCM-এ আটকে গেলে এক ধাপ পিছিয়ে 018-এ যাও — gcd function ঠিকঠাক থাকলে LCM প্রায় বিনা পরিশ্রমে চলে আসে। এটাও মনে রাখার মতো: ভালো একটা building block (এখানে gcd) থাকলে তার উপরে নতুন জিনিস বানানো কত সহজ হয়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল সূত্র একটাই, আর সেটা GCD-র সাথে জড়ানো:
```text
gcd(a, b) × lcm(a, b) = a × b
```
মানে `lcm(a, b) = (a × b) / gcd(a, b)`। যেহেতু GCD আমরা Euclid দিয়ে O(log) সময়ে বের করতে পারি, LCM-ও সেই একই সময়ে বেরিয়ে যায়।
কেন এই সূত্র? Factorization দিয়ে ভাবলে পরিষ্কার: প্রতিটা prime-এর জন্য GCD নেয় **min** power, LCM নেয় **max** power। আর যেকোনো দুই সংখ্যার জন্য `min + max = দুজনের যোগফল` — তাই gcd × lcm-এ প্রতিটা prime-এর power মিলে যায় ঠিক a × b-র সমান।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
GCD-সূত্র মাথায় না এলে, সবচেয়ে সরল চিন্তা — বড় সংখ্যাটার multiple একটা একটা করে বানাও, আর প্রথম যেটা ছোট সংখ্যাটা দিয়েও ভাগ যায়, সেটাই LCM:
```python
def lcm_brute(a, b):
if a == 0 or b == 0:
return 0
bigger = max(a, b)
smaller = min(a, b)
multiple = bigger
while multiple % smaller != 0: # দুজনেরই multiple হলো কি?
multiple += bigger
return multiple
```
এটা bigger-এর multiple একে একে দেখে (bigger, 2×bigger, ...), আর প্রথম যেটা smaller দিয়েও ভাগ যায় সেটাই উত্তর। বড় সংখ্যা থেকে শুরু করায় ছোট দিকটা দ্রুত মেলে। ঠিক উত্তর দেয়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা হলো এই loop সবচেয়ে খারাপ ক্ষেত্রে `smaller` বার পর্যন্ত ঘুরতে পারে। coprime সংখ্যায় (যেমন a = 999999937, b = 999999931, দুটো বড় prime) lcm = a × b, মানে loop প্রায় smaller সংখ্যক বার চলবে।
```text
a, b দুটো ~10^9 আর coprime হলে:
brute force : ~10^9 বার loop (ধীর, O(min(a, b)))
gcd-সূত্র : ~30 ধাপ (gcd) + ১টা ভাগ-গুণ (O(log min(a, b)))
```
মূল কথা: multiple একে একে খোঁজা অপচয়, যখন একটামাত্র সূত্রে সরাসরি উত্তর পাওয়া যায়। সেই সূত্রের চাবি হলো GCD।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **LCM আর GCD পরস্পরের পরিপূরক: `gcd × lcm = a × b`।** তাই GCD জানলেই LCM এক ভাগে বেরোয়।
GCD আমরা 018-এ Euclid দিয়ে O(log) সময়ে বের করতে শিখেছি। তাই:
```python
def lcm(a, b):
return a // gcd(a, b) * b
```
একটাই সূক্ষ্ম কৌশল — **আগে ভাগ, পরে গুণ**। `a // gcd(a, b)` সবসময় পূর্ণসংখ্যা (কারণ gcd নিশ্চিতভাবে a-কে ভাগ করে), তাই আগে ভাগ করলে কোনো ভগ্নাংশের ঝামেলা নেই, আর মাঝপথে অযথা বিশাল সংখ্যা (a × b) তৈরি হয় না।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **LCM আলাদা করে খুঁজতে হয় না — GCD-র সাথে এর একটা সরল সম্পর্ক আছে, তাই একটা জানলেই অন্যটা free।**
আর ছোট্ট practical মোচড়: `a * b // gcd` না লিখে `a // gcd * b` লেখো। দুটো একই উত্তর দেয়, কিন্তু প্রথমটায় `a * b` মাঝপথে বিশাল হয়ে overflow ঝুঁকি বাড়ায় (অন্য ভাষায়), আর Python-এ অযথা বড় সংখ্যা নিয়ে কাজ করে। "আগে ভাগ" — এই এক শব্দের অভ্যাসটা মনে রাখো।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দুই সংখ্যার multiple-এর তালিকা মেলাও — প্রথম মিল কোথায়:
```text
12-এর multiple : 12 24 36 48 60 ...
18-এর multiple : 18 36 54 72 ...
^^
প্রথম common = 36 = lcm(12, 18)
```
এবার সূত্রটা কেন কাজ করে, factorization দিয়ে দেখো (min/max power):
```text
12 = 2^2 · 3^1
18 = 2^1 · 3^2
gcd = প্রতি prime-এর min power = 2^1 · 3^1 = 6
lcm = প্রতি prime-এর max power = 2^2 · 3^2 = 36
যাচাই: gcd × lcm = 6 × 36 = 216 = 12 × 18 ✓
তাই lcm = 12 × 18 / 6 = 36
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো lcm(12, 18) ধীরে চালাই। আগে gcd, তারপর সূত্র:
ধাপ ১ — gcd(12, 18) বের করি (Euclid):
| step | a | b | a % b |
| --- | --- | --- | --- |
| 1 | 12 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 → থামো, gcd = 6 |
ধাপ ২ — সূত্র বসাই (আগে ভাগ, পরে গুণ):
```text
lcm = a // gcd * b
= 12 // 6 * 18
= 2 * 18
= 36
```
যাচাই: 36 = 12×3 = 18×2 — দুজনেরই multiple, আর এর ছোট কোনো common multiple নেই। **lcm = 36**, বাস-স্টপের গল্পের সাথে হুবহু মিলল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def gcd(a, b):
"""018-এর Euclid — LCM-এর ভিত্তি।"""
a, b = abs(a), abs(b)
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""a আর b-এর least common multiple, GCD দিয়ে।"""
if a == 0 or b == 0:
return 0 # 0-এর সাথে common multiple ধরা হয় 0
return abs(a) // gcd(a, b) * abs(b) # আগে ভাগ, পরে গুণ
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert lcm(12, 18) == 36
assert lcm(4, 6) == 12
assert lcm(5, 7) == 35 # coprime -> a × b
assert lcm(6, 12) == 12 # একজন অন্যজনের multiple
assert lcm(10, 10) == 10 # একই সংখ্যা
assert lcm(7, 1) == 7 # 1-এর সাথে -> অন্য সংখ্যাটাই
assert lcm(18, 12) == 36 # ক্রম উল্টে দিলেও একই
assert lcm(0, 5) == 0 # edge case: 0
assert lcm(21, 6) == 42 # gcd 3 -> 21//3*6 = 42
print(lcm(12, 18)) # 36
print(lcm(5, 7)) # 35
print(lcm(6, 12)) # 12
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def gcd(a, b):
a, b = abs(a), abs(b)
while b:
a, b = b, a % b
return a
```
এটা 018-এর সেই Euclid — LCM-এর ভিত্তি। বড় জোড়াকে ছোট জোড়ায় নামিয়ে নামিয়ে `b = 0` হলে `a`-ই gcd।
```text
if a == 0 or b == 0:
return 0
```
Edge case: 0-এর সাথে LCM আমরা 0 ধরি (0 যেকোনো সংখ্যার multiple, তাই "সবচেয়ে ছোট common multiple" 0)। এটা আলাদা করে না সামলালে নিচের সূত্রে `gcd(0, b) = b` দিয়ে ভাগ ঠিক চললেও 0 বেরোত — তবু পরিষ্কার রাখতে আগেই ধরছি।
```text
return abs(a) // gcd(a, b) * abs(b)
```
এটাই হৃদয়। প্রথমে `a // gcd` (নিশ্চিতভাবে পূর্ণসংখ্যা), তারপর `* b`। abs নিচ্ছি যাতে negative input এলেও LCM ধনাত্মক বেরোয়। "আগে ভাগ" — অযথা বিশাল মধ্যবর্তী সংখ্যা এড়াতে।
বাকি `assert` লাইনগুলো নিজেদের চেক করছে; সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
36
35
12
সব test pass!
```
প্রথম তিন লাইন তিনটা `print(lcm(...))` থেকে: (12,18) → 36, (5,7) → 35 (coprime, তাই a×b), (6,12) → 12 (12 হলো 6-এর multiple)। তার আগের সব `assert` চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ integer division নেই, তাই "আগে ভাগ, পরে গুণ"-এর ভাগটা `Math.floor` দিয়ে করি (gcd নিশ্চিতভাবে ভাগ করে, তাই floor নিরাপদ)।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function gcd(a, b) {
a = Math.abs(a); b = Math.abs(b);
while (b) [a, b] = [b, a % b];
return a;
}
function lcm(a, b) {
if (a === 0 || b === 0) return 0; // 0-এর সাথে lcm = 0
return Math.floor(Math.abs(a) / gcd(a, b)) * Math.abs(b); // আগে ভাগ, পরে গুণ
}
// ---- test cases (file-এর example + edge case) ----
assert(lcm(12, 18) === 36, "12,18");
assert(lcm(4, 6) === 12, "4,6");
assert(lcm(5, 7) === 35, "coprime → a*b");
assert(lcm(6, 12) === 12, "multiple");
assert(lcm(10, 10) === 10, "same");
assert(lcm(7, 1) === 7, "with 1");
assert(lcm(18, 12) === 36, "ক্রম উল্টানো");
assert(lcm(0, 5) === 0, "edge 0");
assert(lcm(21, 6) === 42, "gcd 3");
console.log("সব JS test pass!");
```
> **JS টীকা:** `a * b / gcd` না লিখে `Math.floor(a / gcd) * b` লেখো — JS number 2^53-এর বেশি integer ঠিক রাখে না, তাই মাঝপথে `a*b` বিশাল হলে নির্ভুলতা হারায়; "আগে ভাগ" সেটা এড়ায়। সত্যিই বড় সংখ্যায় `BigInt` দরকার।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function gcd(a: number, b: number): number {
a = Math.abs(a); b = Math.abs(b);
while (b !== 0) [a, b] = [b, a % b];
return a;
}
function lcm(a: number, b: number): number {
if (a === 0 || b === 0) return 0;
return Math.floor(Math.abs(a) / gcd(a, b)) * Math.abs(b);
}
function expect(actual: number, expected: number, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const cases: ReadonlyArray