Problem link ও উৎস
- Original source: Classic beginner exercise
- Platform: Classic exercise
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Easy
- Pattern: √n factor pairs
- Basic idea inherited from: 011 (Divisibility Rules)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা positive integer `n` দেওয়া আছে। বলতে হবে তার মোট কতগুলো **factor** (বা divisor) আছে — মানে কতগুলো সংখ্যা `n`-কে নিঃশেষে ভাগ করে।
যেমন `12`-এর factor: 1, 2, 3, 4, 6, 12 — মোট **6**টা। `7`-এর factor: 1, 7 — মোট **2**টা (কারণ 7 prime)।
আমরা শুধু **গুনব** কতগুলো, factor-গুলো ছাপতে হবে না (যদিও চাইলে সহজেই ছাপানো যায়)।
### Input ও output {#6-example-input-and-output}
```text
count_factors(n) — n-এর factor সংখ্যা
-------------------------------------
count_factors(12) -> 6 (1,2,3,4,6,12)
count_factors(7) -> 2 (1,7 — prime, তাই ঠিক 2)
count_factors(1) -> 1 (শুধু 1 নিজে)
count_factors(36) -> 9 (perfect square, বিজোড় সংখ্যা!)
count_factors(16) -> 5 (1,2,4,8,16 — perfect square)
count_factors(100)-> 9 (1,2,4,5,10,20,25,50,100)
```
দুটো মজার সত্য: **prime-এর ঠিক 2টা factor** (1 আর নিজে), আর **perfect square-এর factor সংখ্যা সবসময় বিজোড়** (কারণ মাঝের √n নিজের জোড়া — যেমন 36-এ 6×6)। এই perfect-square কেসটাই এই problem-এর সবচেয়ে দামি ফাঁদ।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো `n`টা ইট দিয়ে তুমি একটা **আয়তক্ষেত্রাকার দেয়াল** বানাতে চাও, একটাও ইট নষ্ট না করে। কত রকম মাপের (লম্বা × চওড়া) দেয়াল বানানো যায়?
- 12টা ইট দিয়ে: `1×12`, `2×6`, `3×4`, `4×3`, `6×2`, `12×1` — প্রতিটা মাপের একটা পাশ একটা factor
- লক্ষ করো — `2×6` আর `6×2` একই দুটো সংখ্যা, শুধু ঘুরিয়ে। তাই অর্ধেক মাপ গুনে **জোড়া ধরে** দ্বিগুণ করলেই হয়
মানে প্রতিটা factor হলো একটা সম্ভাব্য "এক পাশের দৈর্ঘ্য", আর তারা স্বাভাবিকভাবেই জোড়ায় আসে (এক পাশ ঠিক করলে অন্য পাশ আপনিই ঠিক)। √n হলো সেই বর্গাকার দেয়ালের বাহু — তার এপারে খুঁজলেই সব জোড়া ধরা পড়ে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **011 (Divisibility Rules)** থেকে।
011-এ শিখেছিলাম একটা মাত্র চেক — `n % d == 0` মানে `d` ভাগ করে `n`-কে। 012-এ আমরা সেই একই চেক **বারবার** চালাই, প্রতিটা সম্ভাব্য `d`-এর জন্য, আর যতবার True পাই ততবার গুনি:
```
011: n % d == 0 -> d কি factor? (একবার)
012: for d: n % d == 0 -> কতগুলো d factor? (বারবার গুনে)
```
মানে 011 ছিল "ভাগ যায় কিনা" — একটা হ্যাঁ/না; 012 হলো "কতজন ভাগ করে" — সেই হ্যাঁ-গুলো গোনা। 011-এর divisibility চেক না বুঝলে এখানে গোনার ভিত্তিটাই দুর্বল থাকবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **factor রা জোড়ায় আসে**, আর সেই জোড়ার ছোট জনটা সবসময় √n-এর এপারে থাকে।
`d` যদি `n`-এর factor হয়, তবে `n // d`-ও factor (কারণ `d × (n//d) = n`)। তাই factor সবসময় **জোড়ায়** আসে: `(1, 12), (2, 6), (3, 4)` — 12-এর জন্য।
```
12-এর factor জোড়া:
1 × 12 2 × 6 3 × 4
\_____/ \____/ \___/
প্রতিটা জোড়ায় ছোট জন ≤ √12 ≈ 3.46
```
মূল অন্তর্দৃষ্টি: প্রতি জোড়ার **ছোট সদস্য** সবসময় ≤ √n (দুজনেই √n-এর চেয়ে বড় হলে গুণফল n ছাড়িয়ে যেত)। তাই 1 থেকে √n পর্যন্ত খুঁজে প্রতিবার **জোড়াসুদ্ধ** তুলে নিলেই সব factor পাওয়া যায় — পুরো n পর্যন্ত যাওয়ার দরকার নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সৎ, সরাসরি ভাবনা — 1 থেকে `n` পর্যন্ত **প্রতিটা** সংখ্যা দেখি, যেটা ভাগ করে তাকে গুনি:
```python
def count_factors_brute(n):
count = 0
for d in range(1, n + 1): # 1 থেকে n সব দেখো
if n % d == 0: # 011-এর divisibility চেক
count += 1
return count
```
এটা একদম স্বচ্ছ — "factor মানে যে ভাগ করে, তাই সবাইকে জিজ্ঞেস করি কে ভাগ করে।" 011-এর চেক বারবার চালানো ছাড়া কিছু না। ছোট `n`-এ একদম ঠিক।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা একটাই — এই loop ঘোরে **পুরো n বার**:
- `n = 1,000,000` হলে 10 লক্ষ বার loop — তাও হয়তো চলে। কিন্তু `n = 10¹²` (এক লক্ষ কোটি) হলে 10¹² বার — কয়েক **ঘণ্টা** লাগবে, interview-তে নিশ্চিত Time Limit Exceeded।
```text
n = 10^12 হলে:
brute O(n) : 10^12 বার loop -> অসম্ভব (ঘণ্টার হিসাব)
smart O(√n) : 10^6 বার loop -> এক লহমা (~সেকেন্ডের ভগ্নাংশ)
```
কোথায় অপচয়? আমরা √n-এর **ওপারের** factor-গুলো (যেমন 36-এ 9, 12, 18, 36) আলাদা করে খুঁজছি — অথচ ওরা তো এপারের factor-দের (4, 3, 2, 1) জোড়া! একই তথ্য দু'বার খোঁজা। জোড়ার সম্পর্ক কাজে লাগালে অর্ধেকেরও কম কাজে শেষ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **√n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ (i আর n//i) গুনে নাও:**
```python
def count_factors(n):
count = 0
i = 1
while i * i <= n: # √n পর্যন্ত (i*i <= n, sqrt এড়িয়ে)
if n % i == 0:
count += 2 # i আর n//i — জোড়া
if i * i == n:
count -= 1 # perfect square: i আর n//i একই, একবার গোনো
i += 1
return count
```
লক্ষ করো `i * i <= n` লিখছি, `i <= sqrt(n)` নয় — কারণ `i * i` integer হিসাব, float-এর গোলমাল (sqrt-এর rounding) এড়ায়। প্রতিবার factor পেলে **2 যোগ** (জোড়ার দুজন), কিন্তু `i * i == n` হলে (perfect square-এর মাঝবিন্দু) জোড়ার দুজন আসলে একই সংখ্যা — তাই **1 কমিয়ে দিই**।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় এক বাক্যে: **factor জোড়ায় আসে, প্রতি জোড়ার ছোট জন ≤ √n — তাই √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ গুনলেই সব factor, অর্ধেক কাজে।**
ছোট্ট কিন্তু জরুরি tweak এর ভেতরে: **perfect square-এ মাঝের factor (√n) নিজের জোড়া** (36-এ 6×6 = 36) — তাকে দুবার গোনা যাবে না, একবার। এই −1 ভুলে গেলে perfect square-এ উত্তর ঠিক 1 বেশি আসবে।
এই "জোড়া ধরে √n পর্যন্ত" চিন্তা পরের problem-এর শিরদাঁড়া: prime check-এও আমরা একই যুক্তিতে √n পর্যন্তই ভাজক খুঁজব।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 36`-এর factor জোড়াগুলো — √36 = 6-এর দু'পাশে কীভাবে আয়নার মতো সাজানো, দেখো:
```text
i (≤ √n) জোড়ার সঙ্গী n//i
1 <-------> 36
2 <-------> 18
3 <-------> 12
4 <-------> 9
6 <-------> 6 <- √36, জোড়া নিজের সাথে! একবার গোনো
^^^^^^^^^^^^
√n পর্যন্ত খুঁজলেই ডান পাশের সব ধরা পড়ে
মোট: 1,2,3,4,6,9,12,18,36 -> 9টা factor
```
কেন √n-এই থামি, এক বাক্যে:
```text
যদি i > √n আর n//i > √n হতো -> i × (n//i) > n -> অসম্ভব!
তাই প্রতি জোড়ার ছোট জন অবশ্যই ≤ √n
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 36` দিয়ে smart version হাতে চালাই। `i * i <= 36` মানে i যাবে 1..6 পর্যন্ত:
| i | i*i | i*i <= 36? | 36 % i == 0? | count বদল | perfect sq? | count (পরে) |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 1 | হ্যাঁ | হ্যাঁ | +2 | না | 2 |
| 2 | 4 | হ্যাঁ | হ্যাঁ | +2 | না | 4 |
| 3 | 9 | হ্যাঁ | হ্যাঁ | +2 | না | 6 |
| 4 | 16 | হ্যাঁ | হ্যাঁ | +2 | না | 8 |
| 5 | 25 | হ্যাঁ | না (36%5=1) | 0 | — | 8 |
| 6 | 36 | হ্যাঁ | হ্যাঁ | +2 | **হ্যাঁ (−1)** | 9 |
i = 7-এ `49 > 36`, loop থামল। **count = 9** — ঠিক 9টা factor (1,2,3,4,6,9,12,18,36)। লক্ষ করো i = 6-এ +2 করে আবার −1 করলাম, কারণ 6 নিজের জোড়া (6×6=36)। এই −1 না করলে উত্তর ভুল করে 10 হতো।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
import math
def count_factors(n):
"""n-এর factor সংখ্যা — O(√n), জোড়া ধরে।"""
if n < 1:
return 0 # positive n-এর জন্যই সংজ্ঞায়িত
count = 0
i = 1
while i * i <= n:
if n % i == 0:
count += 2 # i আর n // i
if i * i == n:
count -= 1 # perfect square: মাঝের factor একবার
i += 1
return count
def count_factors_brute(n):
"""একই উত্তর, সরল O(n) — যাচাইয়ের জন্য।"""
if n < 1:
return 0
return sum(1 for d in range(1, n + 1) if n % d == 0)
def list_factors(n):
"""বোনাস: factor গুলো sorted তালিকা হিসেবে।"""
small, large = [], []
i = 1
while i * i <= n:
if n % i == 0:
small.append(i)
if i != n // i:
large.append(n // i)
i += 1
return small + large[::-1] # large উল্টে জুড়লে পুরো sorted
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_factors(12) == 6
assert count_factors(7) == 2 # prime -> ঠিক 2
assert count_factors(1) == 1 # শুধু নিজে
assert count_factors(36) == 9 # perfect square -> বিজোড়
assert count_factors(16) == 5 # perfect square
assert count_factors(100) == 9
# সরল আর চালাক — দুই পদ্ধতি সব ছোট n-এ মেলে কিনা
for n in range(1, 200):
assert count_factors(n) == count_factors_brute(n)
assert list_factors(12) == [1, 2, 3, 4, 6, 12]
assert list_factors(36) == [1, 2, 3, 4, 6, 9, 12, 18, 36]
assert len(list_factors(36)) == count_factors(36) # গোনা আর তালিকা মেলে
print(count_factors(12)) # 6
print(count_factors(36)) # 9
print(count_factors(7)) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
if n < 1:
return 0
```
factor গোনা positive সংখ্যার জন্যই অর্থপূর্ণ; 0 বা negative-এ 0 ফেরাই (রক্ষাকবচ)।
```
while i * i <= n:
```
**এই problem-এর প্রাণ।** `i` চলে 1 থেকে √n পর্যন্ত — কিন্তু `sqrt` না ডেকে `i * i <= n` লিখছি, যাতে integer হিসাবেই থাকে আর float rounding-এর ভুল না হয়।
```
if n % i == 0:
count += 2
```
`i` ভাগ করলে (011-এর চেক), জোড়ার দুজন — `i` আর `n // i` — দুটোকেই গুনি, তাই **+2**।
```
if i * i == n:
count -= 1
```
**সবচেয়ে ভোলা লাইন।** perfect square-এ মাঝের factor (√n) নিজের জোড়া (6×6=36), তাই দুবার গোনা চলবে না — একবার **কমিয়ে** দিই।
```
def list_factors(n):
... small.append(i) ... if i != n // i: large.append(n // i)
return small + large[::-1]
```
বোনাস — ছোট factor-দের `small`-এ, বড়দের `large`-এ জমাই; `i != n // i` চেক perfect square-এ মাঝেরটা দুবার ঢোকা আটকায়। শেষে `large[::-1]` (উল্টানো) জুড়লে পুরো তালিকা sorted।
`for n in range(1, 200)` loop-টা চালাক version-কে সরল version-এর সাথে 199টা সংখ্যায় মিলিয়ে যাচাই করে — এই "সরল দিয়ে চালাক verify" এই level-এর সোনার নিয়ম। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
6
9
2
সব test pass!
```
তিনটা লাইন তিনটা `print` থেকে: `count_factors(12)` → 6, `count_factors(36)` → 9 (perfect square, বিজোড়), `count_factors(7)` → 2 (prime)। তার আগে সব `assert` — নির্দিষ্ট কেস, 1..199 জুড়ে দুই পদ্ধতির মিল, আর তালিকা-বনাম-গোনা — চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` মানে O(√n) চালাক version সব ক্ষেত্রে সরল version-এর সমান উত্তর দেয়।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√n)** — loop চলে 1 থেকে √n পর্যন্ত, তাই প্রায় √n বার। `n = 10¹²` হলেও মাত্র 10⁶ ধাপ — সেকেন্ডের ভগ্নাংশ। (brute version O(n) — n = 10¹²-এ অসম্ভব ধীর।) এই O(n) → O(√n) নামানোই এই level-এর কেন্দ্রীয় শিক্ষা।
### অতিরিক্ত জায়গা {#16-space-complexity}
- **`count_factors`:** **O(1)** — শুধু `count`, `i`; কোনো list নেই।
- **`list_factors`:** **O(√n)** (বা মোট factor সংখ্যার সমান) — কারণ factor-গুলো তালিকায় জমা হয়।
শুধু গুনতে হলে O(1) space-ই যথেষ্ট।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **perfect square-এ −1 ভুলে যাওয়া** — এক নম্বর ফাঁদ। 36-এ 6 দুবার গোনা পড়লে উত্তর ভুল করে 10 হয়। `if i * i == n: count -= 1` চাই।
2. **`i <= sqrt(n)` দিয়ে float-ভুল** — `math.sqrt(n)` float দেয়, বড় n-এ rounding-এ একটা factor ফসকাতে বা বাড়তে পারে। সবসময় `i * i <= n` (integer) লেখো।
3. **`range(1, n)` দিয়ে n-কে বাদ** — n নিজেও তো নিজের factor; brute-এ `range(1, n+1)` লাগে।
4. **`+2`-এর বদলে `+1` করা** — √n পর্যন্ত খুঁজলে প্রতিবার **জোড়া** (i ও n//i) পাও, তাই +2; শুধু +1 করলে √n-এর ওপারের factor-গুলো বাদ পড়বে।
5. **n = 1 ভুল হওয়া** — `i=1, 1*1<=1` সত্যি, `1%1==0` → +2, কিন্তু `1*1==1` → −1, মোট 1। ঠিক (1-এর factor শুধু নিজে)। কিন্তু hand-rolled version-এ সাবধান না হলে এটা গুলিয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **013 — Check Prime** (এই repo) — prime মানে ঠিক 2টা factor; এই √n loop-এ একটাও ভাজক পেলেই composite — সরাসরি পরের ধাপ।
- **024 — Number of Divisors** (এই repo) — বড় সংখ্যায় factorization থেকে `(e₁+1)(e₂+1)...` সূত্রে divisor গোনা; এই √n গোনার গণিত-রূপ। সম্পর্কিত: **CSES — Counting Divisors** (