024 — Number of Divisors¶

016-এ prime factorization শিখেছ — এবার তার একটা অসাধারণ ফল: factorization জানলে divisor গুনতে আর একটাও divisor খুঁজতে হয় না, শুধু exponent থেকে একটা গুণফলেই উত্তর। ধীরে পড়ো — (e₁+1)(e₂+1)... কেন কাজ করে, সেই "choice গোনা" idea-টা Level 3-এর combinatorics-এরও আগাম দর্শন।

Source¶

Original source: CSES Problem Set — Counting Divisors
Platform: CSES — https://cses.fi/problemset/task/1713
Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
Difficulty: Medium
Pattern: exponent formula — d(n) = ∏(eᵢ + 1)
Basic idea inherited from: 016 — Prime Factorization

1. Problem in simple words¶

একটা ধনাত্মক integer n দেওয়া আছে। বের করতে হবে n-এর মোট কয়টা divisor (গুণনীয়ক) আছে — মানে 1 থেকে n পর্যন্ত (n সহ) কয়টা সংখ্যা n-কে নিঃশেষে ভাগ করে।

উদাহরণ: 12-এর divisor হলো 1, 2, 3, 4, 6, 12 — মোট 6টা। তাই d(12) = 6।

কয়েকটা সীমা: প্রতিটা সংখ্যার অন্তত 2টা divisor (1 আর সে নিজে), শুধু 1-এর একটাই (নিজে)। আর prime-এর ঠিক 2টা।

2. What is the math idea?¶

মূল idea factorization থেকে আসা একটা product formula। n-কে prime-এর power-এ লিখলে n = p₁^e₁ · p₂^e₂ · ..., তাহলে:

d(n) = (e₁ + 1) · (e₂ + 1) · ...

মানে প্রতিটা prime-এর exponent-এর সাথে 1 যোগ করে সব গুণ করো।

কেন? একটা divisor বানাতে হলে প্রতিটা prime থেকে "কয়টা power নেব" বেছে নিতে হয়। p₁ থেকে নিতে পারি 0, 1, 2, ..., e₁ — মোট (e₁ + 1) রকম পছন্দ। প্রতিটা prime-এর পছন্দ স্বাধীন (independent), তাই মোট divisor = সব পছন্দের গুণফল। এটা আসলে Level 3-এর multiplication principle-এর আগাম রূপ।

3. Which basic idea does this inherit from?¶

এটা সরাসরি 016 (Prime Factorization)-এর উপর দাঁড়িয়ে। divisor গোনার formula চালাতে আগে n-এর প্রতিটা prime আর তার exponent জানা চাই — সেটাই 016-এর কাজ। আমরা ছোট prime দিয়ে n-কে খোসা ছাড়িয়ে প্রতিটা prime কতবার এল (exponent) গুনি, তারপর (e+1) গুলো গুণ করি।

মূল পার্থক্য: 016 দেয় factorization (কোন prime কয়বার); 024 সেই exponent থেকে এক ধাপে divisor সংখ্যা বের করে। তাই factorization-এ আটকালে এক ধাপ পিছিয়ে 016-এ যাও।

4. Real-life analogy¶

ভাবো তুমি একটা পিৎজা অর্ডার করছ, আর তিন রকম topping আছে যেগুলো তুমি 0 থেকে কিছু সর্বোচ্চ পরিমাণ পর্যন্ত নিতে পারো — ধরো cheese 0-3 চামচ, olive 0-2 চামচ, mushroom 0-1 চামচ। কত রকম আলাদা পিৎজা বানানো সম্ভব?

cheese-এ 4 রকম পছন্দ (0,1,2,3), olive-এ 3 রকম (0,1,2), mushroom-এ 2 রকম (0,1)। প্রতিটা স্বাধীন, তাই মোট = 4 × 3 × 2 = 24 রকম পিৎজা।

ঠিক এভাবেই divisor বানানো: প্রতিটা prime হলো এক-একটা topping, exponent হলো তার সর্বোচ্চ পরিমাণ, আর প্রতিটা divisor হলো এক-একটা আলাদা পিৎজা। n = 2³·3²·5¹-এর divisor সংখ্যা = 4 × 3 × 2 = 24।

5. Visual explanation¶

প্রথমে n = 12-এর সব divisor হাতে লিখি — জোড়ায় জোড়ায় আসে:

12-এর divisor (জোড়ায়):
  1 × 12     2 × 6     3 × 4
  -> 1, 2, 3, 4, 6, 12  ->  মোট 6টা

এবার formula কীভাবে একই 6 দেয় (exponent থেকে choice গোনা):

12 = 2^2 · 3^1

2-এর power বাছো: 2^0, 2^1, 2^2   -> 3 রকম  (= 2+1)
3-এর power বাছো: 3^0, 3^1        -> 2 রকম  (= 1+1)

d(12) = 3 × 2 = 6   ✓

প্রতিটা combination একটা divisor:
 2^0·3^0=1   2^1·3^0=2   2^2·3^0=4
 2^0·3^1=3   2^1·3^1=6   2^2·3^1=12

6. Example input and output¶

   n   ->  d(n)   factorization
-----------------------------------------
   1   ->   1     (খালি; কোনো prime নেই)
   2   ->   2     2^1 -> (1+1)
   6   ->   4     2·3 -> (1+1)(1+1)
  12   ->   6     2^2·3 -> (2+1)(1+1)
  16   ->   5     2^4 -> (4+1)
  36   ->   9     2^2·3^2 -> (2+1)(2+1)
  37   ->   2     prime -> (1+1)
  360  ->  24     2^3·3^2·5 -> 4·3·2

দুটো জিনিস খেয়াল করো: prime-এর ঠিক 2টা divisor (37 → 2)। আর perfect power-এর divisor বিজোড় হয় — 36 (= 6²) → 9টা, কারণ একটা divisor (এখানে 6) তার জোড়া নিজেই; বাকিরা জোড়ায়।

7. Brute force thinking¶

factorization-formula মাথায় না এলে, সবচেয়ে সরল — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা দিয়ে n ভাগ করে দেখি, ভাগ গেলে divisor, গুনি:

def count_divisors_brute(n):
    count = 0
    for d in range(1, n + 1):
        if n % d == 0:
            count += 1
    return count

এটা একদম সংজ্ঞা: 1..n-এর প্রতিটা d-র জন্য n % d == 0 হলে divisor, count বাড়াই। সরল, ঠিক উত্তর। (একটু চালাক brute force: √n পর্যন্ত খুঁজে জোড়াসুদ্ধ গোনা — 012-এর কৌশল, O(√n)। কিন্তু এখানে আমরা formula-ভিত্তিক পথ দেখব, যেটা factorization জানা থাকলে আরও তথ্যপূর্ণ।)

8. Why brute force may be slow¶

এই সরল loop ঠিক n বার ঘোরে। ছোট n-এ ঠিক আছে, কিন্তু n বিশাল হলে অসম্ভব:

n = 10^6      -> 10^6 বার         (ঠিক আছে)
n = 10^9      -> 10^9 বার         (ধীর)
n = 10^12     -> 10^12 বার        (অসম্ভব — TLE; যেমন CSES-এ n বড়)

√n / formula  -> n=10^12 হলেও ~10^6 ধাপ  (এক লহমায়)

মূল সমস্যা: 1..n পুরোটা ঘোরা। অথচ divisor-রা √n-এর এপারে জোড়ায় বসে (012), আর factorization-ও √n-এই শেষ। তাই formula পথে কাজ √n-এ নেমে আসে — n যত বড়ই হোক।

9. Better thinking¶

মূল insight — divisor গুনতে প্রতিটা সম্ভাব্য divisor খুঁজতে হয় না; n-এর factorization জানলে exponent থেকে এক গুণফলেই উত্তর।

আমরা factorize করার সময়ই (016-এর মতো) প্রতিটা prime-এর exponent গুনি, আর সাথে সাথে (e + 1) গুণ করে চলি:

def count_divisors(n):
    count = 1
    p = 2
    while p * p <= n:
        if n % p == 0:
            e = 0
            while n % p == 0:        # এই prime কতবার? -> exponent
                n //= p
                e += 1
            count *= (e + 1)         # এই prime থেকে (e+1) রকম পছন্দ
        p += 1
    if n > 1:                        # বাকি n নিজেই একটা prime (exponent 1)
        count *= 2                   # (1 + 1)
    return count

মূল চালাকি: factorization আর গোনা একসাথে — আলাদা করে divisor list বানানোর দরকারই নেই। আর শেষের if n > 1 (exponent 1, তাই × 2) — n-এর বড় prime factor ধরার জন্য।

10. Thinking tweak¶

আসল "আহা!" মুহূর্ত: প্রতিটা divisor আসলে "প্রতিটা prime থেকে কত power নেব"-এর একটা পছন্দ; তাই divisor গোনা = পছন্দ গোনা = (e+1) গুলোর গুণফল।

মূল মোচড়টা হলো divisor-দের একটা একটা করে না খুঁজে, তাদের "গঠনের নিয়ম" দেখা। n = p₁^e₁ · ...-এর প্রতিটা divisor p₁^a · p₂^b · ... রূপের, যেখানে 0 ≤ a ≤ e₁, ইত্যাদি। প্রতিটা exponent-এর জন্য (e+1) রকম স্বাধীন পছন্দ — তাই গুণ। এই "independent choice → গুণ" নিয়মটা মাথায় গাঁথো; Level 3-এ পুরো combinatorics এর উপর দাঁড়াবে।

11. Step-by-step dry run¶

চলো count_divisors(12) ধীরে চালাই। শুরুতে count = 1, n = 12:

p	n % p == 0?	ভেতরের while: n হয়, e হয়	count বদল	count
2	হ্যাঁ	12→6→3, e = 2	1 × (2+1)	3
3	3·3 > 3, loop শেষ	—	—	3

Loop-এর পরে n = 3 > 1, তাই বাকি 3 একটা prime (exponent 1): count *= 2 → 3 × 2 = 6।

d(12) = 6 — section 5-এর হাতে-গোনা 1,2,3,4,6,12-এর সাথে হুবহু মিলল। লক্ষ করো: 2-এর exponent 2 → (2+1) = 3; 3-এর exponent 1 → (1+1) = 2; গুণফল 6।

12. Python solution¶

def count_divisors(n):
    """n-এর মোট divisor সংখ্যা — exponent formula d(n) = ∏(eᵢ + 1)।"""
    if n <= 0:
        return 0
    count = 1
    p = 2
    while p * p <= n:
        if n % p == 0:
            e = 0
            while n % p == 0:         # exponent গোনা
                n //= p
                e += 1
            count *= (e + 1)
        p += 1
    if n > 1:                         # বাকি n নিজেই prime (exponent 1)
        count *= 2
    return count


def count_divisors_brute(n):
    """সংজ্ঞা ধরে: 1..n-এ ভাগ গোনা — formula verify করতে।"""
    return sum(1 for d in range(1, n + 1) if n % d == 0)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_divisors(1) == 1
assert count_divisors(2) == 2
assert count_divisors(6) == 4
assert count_divisors(12) == 6
assert count_divisors(16) == 5          # 2^4 -> 5
assert count_divisors(36) == 9          # perfect square -> বিজোড়
assert count_divisors(37) == 2          # prime
assert count_divisors(360) == 24        # 2^3·3^2·5
assert count_divisors(7919) == 2        # বড় prime

# formula আর brute force ছোট range-এ মিলছে কি না
for m in range(1, 200):
    assert count_divisors(m) == count_divisors_brute(m)

print(count_divisors(12))    # 6
print(count_divisors(36))    # 9
print(count_divisors(360))   # 24
print("সব test pass!")

13. Line-by-line explanation¶

    count = 1
    p = 2
    while p * p <= n:

count শুরুতে 1 (গুণফলের neutral মান)। তারপর √n পর্যন্ত প্রতিটা সম্ভাব্য prime p দেখি (factorization-এর মতো — কোনো prime factor √n-এর এপারে অবশ্যই থাকে, বড়জোর একটা ছাড়া)।

        if n % p == 0:
            e = 0
            while n % p == 0:
                n //= p
                e += 1

p যদি n-কে ভাগ করে, ভেতরের while দিয়ে গুনি p কতবার যায় — সেটাই exponent e। সাথে সাথে n থেকে সব p সরিয়ে ফেলি।

            count *= (e + 1)

এটাই formula-র হৃদয়: এই prime থেকে (e+1) রকম পছন্দ, তাই count-কে (e+1) দিয়ে গুণ।

    if n > 1:
        count *= 2

Loop শেষে n যদি এখনো 1-এর বেশি হয়, সেটা n-এর বড় prime factor (exponent 1), তাই (1+1) = 2 দিয়ে গুণ। (যেমন n = 14 = 2×7: loop-এ 2 ধরা পড়ে count = 2, তারপর n = 7 এই লাইনে count = 4।)

count_divisors_brute সংজ্ঞা ধরে গোনে; for m in range(1, 200) loop দুই version মিলিয়ে formula-র correctness যাচাই করে। সব ঠিক থাকলে শেষে সব test pass!।

14. Output walkthrough¶

চালালে যা ছাপবে:

6
9
24
সব test pass!

প্রথম লাইন: d(12) = 6 (section 11-এর dry run)। দ্বিতীয়: d(36) = 9 — 36 = 2²·3² → (2+1)(2+1) = 9, perfect square তাই বিজোড়। তৃতীয়: d(360) = 24 — 360 = 2³·3²·5 → 4·3·2 = 24। তার আগে সব assert, এমনকি 1..199 জুড়ে formula-vs-brute মিল — সব চুপচাপ pass, তাই শেষে সব test pass!।

15. Time complexity¶

O(√n) — মূল loop p চলে 2 থেকে √n পর্যন্ত (factorization-এর খরচ); ভেতরের while-গুলো মিলিয়েও মোট কাজ O(√n)-এই থাকে। তাই n = 10¹² হলেও √n = 10⁶ — এক লহমায় শেষ। সরল brute force-এর O(n)-এর তুলনায় বিশাল উন্নতি।

16. Space complexity¶

O(1) — শুধু count, p, e, আর পরিবর্তিত n — গুটিকয় variable। divisor-দের কোনো list বানাচ্ছি না, শুধু গুনছি। input ছাড়া আলাদা জায়গা প্রায় শূন্য।

17. Common mistakes¶

count 0 থেকে শুরু করা — এটা গুণফল, তাই neutral মান 1 থেকে শুরু; 0 থেকে শুরু করলে উত্তর সবসময় 0।
e না (e + 1) দিয়ে গুণ — মনে রেখো প্রতিটা prime-এ পছন্দ 0..e মানে (e+1) রকম, শুধু e নয়। 12-এ 2-এর জন্য 3 (0,1,2), 2 নয়।
শেষের if n > 1 ভুলে যাওয়া — n-এর বড় prime factor (যেমন 14-এর 7, বা 7919) এই লাইন ছাড়া গোনা হয় না, উত্তর কম আসে।
divisor list বানিয়ে memory নষ্ট — শুধু সংখ্যা চাইলে list বানানোর দরকার নেই; exponent গুণফলই যথেষ্ট।
n = 1 ভুলে যাওয়া — 1-এর কোনো prime factor নেই, loop চলে না, count থাকে 1 — যা ঠিক (1-এর একটাই divisor)।

18. Harder problems that inherit this idea¶

CSES — Counting Divisors (https://cses.fi/problemset/task/1713) — অনেকগুলো n-এর জন্য divisor গোনা; বড় হলে SPF sieve দিয়ে দ্রুত (017-এর কৌশল)।
CSES — Divisor Analysis (https://cses.fi/problemset/task/2182) — divisor count, sum, product একসাথে; এই formula-র সম্প্রসারণ।
025 (Sum of Divisors) — এই repo-রই পরের ধাপ, যেখানে একই factorization থেকে divisor-দের যোগফল বের করব।

19. Pattern learned¶

Divisor count via exponents — d(n) = ∏(eᵢ + 1)। মূল reusable টুকরো: factorization + প্রতিটা exponent-এ (e+1) গুণ; শেষে if n > 1 হলে × 2। আর বড় শিক্ষা: "independent choice গোনা = গুণ করা" — Level 3-এর combinatorics-এর বীজ।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "divisor সংখ্যা = factorize করো, প্রতিটা exponent-এ count *= (e+1), শেষে n>1 হলে × 2। 'কয়টা গুণনীয়ক' দেখলেই exponent formula মনে করব — O(√n), আর এটাই combinatorics-এর multiplication principle-এর প্রথম দেখা।"

পরের ধাপ → 025 — Sum of Divisors (একই factorization থেকে এবার যোগফল)। শিকড় → 016 — Prime Factorization।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি করা হয়নি — বরং "common interview pattern" লেখা হয়েছে।