Problem link ও উৎস
- Original source: Classic exercise (related: Project Euler 3 —
)
- Platform: Classic exercise / Project Euler (related)
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Medium
- Pattern: peeling primes
- Basic idea inherited from: 013 (Check Prime)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer `n` (≥ 2) দেওয়া আছে। তাকে **prime-দের গুণফল** হিসেবে লিখতে হবে — প্রতিটা prime কতবার আসে সেটাসহ।
যেমন:
- `12 = 2 × 2 × 3 = 2² × 3` → `{2: 2, 3: 1}`
- `360 = 2³ × 3² × 5` → `{2: 3, 3: 2, 5: 1}`
- `7 = 7` (prime নিজেই) → `{7: 1}`
মূল গণিত-সত্য (Fundamental Theorem of Arithmetic): প্রতিটা সংখ্যা ঠিক **একভাবেই** prime-দের গুণফলে লেখা যায় — এটাই তার অনন্য DNA।
### Input ও output {#6-example-input-and-output}
```text
factorize(n)
-----------------------------------------
factorize(12) -> {2: 2, 3: 1} (2² × 3)
factorize(360) -> {2: 3, 3: 2, 5: 1}
factorize(7) -> {7: 1} (prime নিজেই)
factorize(2) -> {2: 1}
factorize(97) -> {97: 1} (বড় prime — শেষের if n>1 ধরে)
factorize(2*7919) -> {2: 1, 7919: 1} <-- 7919 বড় prime, শেষে ধরা পড়ে
```
সবচেয়ে দামি edge case শেষ দুটো: **prime সংখ্যা** (যেমন 97) — loop-এ কিছুই কাটে না, শেষে `n > 1` থেকেই `{97: 1}` আসে; আর **এক বড় prime factor** (`2 × 7919`) — loop শুধু 2 ধরে, 7919 √n-এর ওপারে বলে loop-এ ধরা পড়ে না, শেষের `if n > 1` তাকে তুলে নেয়। এই অংশ ভুলে গেলে বড় prime factor হারিয়ে যায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **পেঁয়াজ**, আর তুমি একটা একটা স্তর (layer) ছাড়াচ্ছ — কিন্তু এই পেঁয়াজের নিয়ম হলো, একই রকম স্তর পরপর জড়ো থাকে।
- সবচেয়ে বাইরের একই রকম স্তর (2-এর স্তর) — যতগুলো আছে সব একসাথে ছাড়াও, গুনে রাখো "2 তিনবার ছিল"
- তারপর পরের রকম স্তর (3-এর স্তর) — সেগুলোও সব ছাড়াও, গুনো
- ... যতক্ষণ পেঁয়াজ শেষ না হয়
`360` ছাড়ালে: প্রথমে 2 তিনবার (`360→180→90→45`), তারপর 3 দু'বার (`45→15→5`), শেষে 5 একবার — পেঁয়াজ শেষ। DNA: `2³ × 3² × 5`। প্রতিটা "রকম স্তর" একটা prime, কতবার আছে সেটা তার power।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **013 (Check Prime)** থেকে।
013-এ আমরা √n পর্যন্ত trial division করে দেখতাম **একটাও** ভাজক আছে কিনা (থাকলে composite)। 016-এ সেই একই trial division, কিন্তু থামি না — ভাজক পেলে তাকে **ছেঁকে বের করি** (ভাগ করে ফেলি), আর গুনে রাখি কতবার:
```
013: ভাজক পেলেই থামো -> "composite" বলে শেষ
016: ভাজক পেলে ভাগ করো, গোনো -> পুরো DNA বের করো
```
মানে 013 ছিল হ্যাঁ/না (prime কিনা); 016 হলো "তবে কোন কোন prime দিয়ে তৈরি?" — এক ধাপ গভীরে। 013-এর √n trial division না বুঝলে এখানকার peeling loop-ও আবছা থাকবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **ছোট prime দিয়ে খোসা ছাড়ানো (peeling)**। সবচেয়ে ছোট prime (2) দিয়ে যতবার নিঃশেষে ভাগ যায় ততবার ভাগ করো, গুনে রাখো; তারপর পরের সংখ্যা (3), তারপর পরের... √n পর্যন্ত।
```
p = 2 থেকে শুরু
যতক্ষণ p*p <= n:
যতক্ষণ n % p == 0: # এক prime নিঃশেষে ছাড়াও
factors[p] += 1
n //= p
p += 1
যদি n > 1: # যা বাকি, সে নিজেই একটা বড় prime
factors[n] += 1
```
দুটো গভীর সত্য: (১) p prime কিনা check করার দরকার নেই — composite p-তে পৌঁছানোর আগেই তার prime factor-রা n থেকে সব ছেঁকে নিয়েছে; (২) শেষে `n > 1` থাকলে সেটাই অবশিষ্ট বড় prime।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল ভাবনা — 2 থেকে `n` পর্যন্ত প্রতিটা সংখ্যা দিয়ে যতবার পারো ভাগ করো:
```python
def factorize_brute(n):
factors = {}
p = 2
while p <= n: # n পর্যন্ত সব
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
p += 1
return factors
```
এটা ঠিক উত্তর দেয় — p যখন একটা prime factor, তখন while-এ সব power ছেঁকে নেয়; composite p-তে আর কিছু কাটে না (আগেই ছাঁকা)। সহজ, পরিষ্কার, ছোট n-এ একদম চলে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা — বাইরের loop `p` চলে প্রায় **n পর্যন্ত**:
- `n` যদি বড় prime হয় (যেমন 1,000,000,007), তাহলে কোনো ছোট p ভাগ করে না, p একে একে n পর্যন্ত বাড়ে — প্রায় 100 কোটি ধাপ। অথচ √n পর্যন্ত গেলেই হতো।
```text
n = 1000000007 (বড় prime) হলে:
brute O(n) : ~10^9 বার p বাড়ে -> অসম্ভব ধীর
√n O(√n) : ~31623 ধাপেই শেষ -> চোখের নিমেষে (শেষে if n>1 ধরে)
```
কোথায় অপচয়? p যখন √n ছাড়িয়ে যায়, তখন n-এর বড়জোর **একটাই** prime factor বাকি থাকতে পারে (দুটো থাকলে গুণফল n ছাড়াত)। তাই √n-এর পর আর loop চালানোর দরকার নেই — যা বাকি, সেটাই অবশিষ্ট prime। এই উপলব্ধিই brute-কে O(√n)-এ নামায়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **√n পর্যন্ত peeling, তারপর যা বাকি সেটাই শেষ prime:**
```python
def factorize(n):
factors = {}
p = 2
while p * p <= n: # √n পর্যন্ত
while n % p == 0: # এক prime নিঃশেষে ছাড়াও
factors[p] = factors.get(p, 0) + 1
n //= p
p += 1
if n > 1: # অবশিষ্ট n নিজেই বড় prime
factors[n] = factors.get(n, 0) + 1
return factors
```
লক্ষ করো — `p * p <= n` (√n, integer compare), আর n প্রতিবার ভাগ হয়ে **ছোট** হয়, তাই √n-ও কমে যায় (loop আরও তাড়াতাড়ি থামে)। আর সেই দুই মণিমুক্তো: (১) p prime কিনা যাচাই করিনি — দরকার নেই; (২) `if n > 1` শেষের বড় prime ধরে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় তিন স্তরে, প্রতিটাই "আহা":
- **ছোট থেকে বড় peeling:** সবচেয়ে ছোট prime দিয়ে আগে সব ছেঁকে নাও — এতে p যখন কোনো সংখ্যায় পৌঁছায়, তার ছোট prime factor সব আগেই বেরিয়ে গেছে। তাই **composite p দিয়ে কখনো ভাগ মেলে না** — p prime কিনা check করাই অপ্রয়োজনীয়!
- **√n যথেষ্ট + একটা ব্যতিক্রম:** √n পর্যন্ত সব ছোট prime ধরা পড়ে; কিন্তু একটা বড় prime factor (> √n) loop-এ ফসকে যেতে পারে — তাকে শেষে `if n > 1` দিয়ে তুলে নাও।
- **n ছোট হতে থাকে:** ভাগের সাথে সাথে n কমে, তাই `p*p <= n`-এর সীমাও নামে — দ্বিগুণ লাভ।
এই "ছোট prime আগে ছাঁকলে composite নিয়ে ভাবতেই হয় না, আর শেষে যা বাকি সেটাই prime" — এই অন্তর্দৃষ্টি factorization-এর প্রাণ।
### ছবিতে বোঝা {#5-visual-explanation}
`360`-এর খোসা ছাড়ানো ধাপে ধাপে — কোন prime কতবার, পাশে দেখো:
```text
n = 360
p=2: 360 % 2=0 -> 180 -> 90 -> 45 (2 তিনবার ছাড়ালাম) factors={2:3}
45 % 2 = 1 (আর 2 নেই), p বাড়াও
p=3: 45 % 3=0 -> 15 -> 5 (3 দু'বার) factors={2:3, 3:2}
5 % 3 = 2 (আর 3 নেই), p বাড়াও
p=4: 4*4=16 <= 5? না -> loop শেষ
শেষে: n = 5 > 1 -> 5 নিজেই prime factors={2:3, 3:2, 5:1}
ফলাফল: 360 = 2³ × 3² × 5
```
লক্ষ করো p=4-এ পৌঁছানোর আগেই 2 সব ছেঁকে গেছে — তাই composite 4 দিয়ে কখনো ভাগ মেলে না, p prime কিনা যাচাই লাগেনি!
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 360` দিয়ে Section 9-এর version হাতে চালাই:
| p | p*p <= n? | ভেতরের while (n % p == 0) | n হয়ে যায় | factors |
| --- | --- | --- | --- | --- |
| 2 | 4 <= 360 ✓ | 360→180→90→45 (3 বার) | 45 | {2: 3} |
| 3 | 9 <= 45 ✓ | 45→15→5 (2 বার) | 5 | {2: 3, 3: 2} |
| 4 | 16 <= 5? ✗ | — (loop থামল) | 5 | {2: 3, 3: 2} |
| শেষে | — | `n = 5 > 1` → তুলে নাও | — | {2: 3, 3: 2, 5: 1} |
বাইরের loop p=4-এ থামল (16 > 5)। তারপর `if n > 1` — n = 5 এখনো 1-এর বেশি, তাই 5-কে factor হিসেবে যোগ। চূড়ান্ত **{2: 3, 3: 2, 5: 1}** = `360 = 2³ × 3² × 5`। লক্ষ করো — 5 কিন্তু loop-এ ধরা পড়েনি (p 4-এ থেমে গেছে), শেষের `if n > 1` তাকে তুলল। এই অংশ বাদ দিলে উত্তরে 5 থাকত না।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def factorize(n):
"""n (>= 2)-এর prime factorization — {prime: power}, O(√n)।"""
factors = {}
p = 2
while p * p <= n:
while n % p == 0: # এক prime নিঃশেষে ছাড়াও
factors[p] = factors.get(p, 0) + 1
n //= p
p += 1
if n > 1: # অবশিষ্ট = বড় prime
factors[n] = factors.get(n, 0) + 1
return factors
def factorize_list(n):
"""একই factorization, কিন্তু flat list হিসেবে (12 -> [2, 2, 3])।"""
out = []
p = 2
while p * p <= n:
while n % p == 0:
out.append(p)
n //= p
p += 1
if n > 1:
out.append(n)
return out
def product(factors):
"""{prime: power} গুণ করে আবার মূল সংখ্যা — যাচাইয়ের জন্য।"""
result = 1
for p, e in factors.items():
result *= p ** e
return result
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert factorize(12) == {2: 2, 3: 1}
assert factorize(360) == {2: 3, 3: 2, 5: 1}
assert factorize(7) == {7: 1} # prime নিজেই
assert factorize(2) == {2: 1}
assert factorize(97) == {97: 1} # বড় prime — শেষের if n>1
assert factorize(2 * 7919) == {2: 1, 7919: 1} # বড় prime factor ধরা
assert factorize_list(12) == [2, 2, 3]
# গুণ করে ফিরে পেলে মূল সংখ্যা? (factorization সঠিক কিনা — সোনার যাচাই)
for n in range(2, 500):
assert product(factorize(n)) == n
print(factorize(12)) # {2: 2, 3: 1}
print(factorize(360)) # {2: 3, 3: 2, 5: 1}
print(factorize(97)) # {97: 1}
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
p = 2
while p * p <= n:
```
p শুরু 2 (সবচেয়ে ছোট prime) থেকে; বাইরের loop √n পর্যন্ত (`p * p <= n`, integer)। p একে একে বাড়বে।
```
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
```
**peeling-এর হৃদয়।** ভেতরের while — যতক্ষণ p নিঃশেষে ভাগ করে, ততবার p-কে গুনি (`factors.get(p, 0) + 1` মানে "আগের গোনা + 1", না থাকলে 0 থেকে শুরু) আর n থেকে p ছেঁকে ফেলি (`n //= p`)। এক prime সম্পূর্ণ বেরোলে তবেই বাইরের loop p বাড়ায়।
```
p += 1
```
পরের সম্ভাব্য factor। (composite p-তে ভেতরের while চলবেই না, কারণ ছোট prime আগেই সব ছেঁকেছে — তাই p prime কিনা যাচাই অপ্রয়োজনীয়।)
```
if n > 1:
factors[n] = factors.get(n, 0) + 1
```
**সবচেয়ে ভোলা, অথচ জরুরি অংশ।** loop শেষে n যদি এখনো 1-এর বেশি থাকে, তবে সেটা একটা বড় prime (> √n) যা loop-এ ধরা পড়েনি — তাকে factor হিসেবে যোগ করি।
`product(factors)` — factor-গুলো গুণ করে মূল সংখ্যা ফিরে আসে কিনা দেখে; `for n in range(2, 500)` এই গুণফল-যাচাই 498টা সংখ্যায় চালায় (factorization সঠিক হলেই গুণফল = মূল n)। এটা সবচেয়ে শক্তিশালী যাচাই। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
{2: 2, 3: 1}
{2: 3, 3: 2, 5: 1}
{97: 1}
সব test pass!
```
তিনটা লাইন তিনটা `print` থেকে: `factorize(12)` → 2²×3, `factorize(360)` → 2³×3²×5, `factorize(97)` → {97:1} (বড় prime, শেষের `if n>1` ধরল)। তার আগে সব `assert` — নির্দিষ্ট কেস (prime, বড় prime factor সহ), আর 2..499 জুড়ে গুণফল = মূল সংখ্যা — চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` মানে factorization সব ক্ষেত্রে সঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√n)** — বাইরের loop সর্বোচ্চ √n পর্যন্ত; প্রতিটা ভাগ n-কে ছোট করে (তাই বাস্তবে আরও দ্রুত)। ভেতরের while-এর মোট কাজও সীমিত — n বারবার অর্ধেক/তৃতীয়াংশ হয়, তাই সব মিলিয়ে O(√n)-এর মধ্যেই। বড় prime 10⁹-এও ~31623 ধাপ। (brute O(n) — বড় prime-এ অসম্ভব।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(log n)** (factor সংখ্যার সমান) — একটা সংখ্যার distinct prime factor সর্বোচ্চ ≈ log₂ n টা (প্রতিটা অন্তত 2, গুণফল n), তাই dictionary-তে এর বেশি ঘর লাগে না। peeling নিজে শুধু গুটিকয় variable নেয়; মূল জায়গা ফলাফল dictionary-তে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **শেষের `if n > 1` ভুলে যাওয়া** — এক নম্বর ফাঁদ। `2 × 7919`-এ loop শুধু 2 ধরবে, 7919 (বড় prime) বাদ পড়বে; `if n > 1` তাকে তোলে। এটা ছাড়া বড় prime factor হারায়।
2. **p prime কিনা আলাদা check করা** — অপ্রয়োজনীয়! ছোট prime আগে ছেঁকে নেওয়ায় composite p-তে ভেতরের while চলবেই না। বাড়তি check শুধু কোড ভারী করে।
3. **`p * p <= n`-এর বদলে `p <= n`** — তাহলে O(n), বড় prime-এ TLE; √n পর্যন্তই যথেষ্ট (শেষে if n>1)।
4. **ভেতরের while-এ `n //= p` ভুলে যাওয়া** — n না কমলে `while n % p == 0` কখনো থামবে না → infinite loop।
5. **n = 1 বা n < 2 নিয়ে দ্বিধা** — 1-এর কোনো prime factor নেই (`{}` ফেরাই); এই solution n ≥ 2 ধরে কাজ করে। 1 দিলে loop চলে না, `if n > 1`-ও মিথ্যা, তাই `{}` — যা ঠিক।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **017 — Smallest Prime Factor (SPF) sieve** (এই repo) — একটা সংখ্যা নয়, অনেক সংখ্যা factorize করতে হলে SPF precompute করে O(log n)-এ; এই peeling-এর দ্রুততর রূপ।
- **023 — Euler Phi** আর **024 — Number of Divisors** (এই repo) — দুটোই factorization-এর exponent থেকে formula (`∏(1-1/p)`, `∏(eᵢ+1)`); এই DNA পেলে সরাসরি প্রয়োগ।
- **Project Euler 3** (