012 — Count Factors¶
011-এ তুমি শিখেছ "একটা সংখ্যা আরেকটা দিয়ে ভাগ যায় কিনা" (
a % b == 0)। আজ সেই চেক দিয়েই বড় প্রশ্ন — একটা সংখ্যার মোট কতগুলো factor (divisor) আছে? প্রথমে সরল ভাবে সব সংখ্যা ঘেঁটে গুনব, তারপর এই level-এর সবচেয়ে দামি কৌশল শিখব: O(n) loop-কে O(√n)-এ নামানো। এই √n trick একবার হাতে এলে prime check, factorization — সব জায়গায় ফিরবে। তাই ধীরে, factor-জোড়ার ছবিটা নিজে হাতে আঁকো।
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)
প্রশ্ন ও উদাহরণ¶
সহজ করে প্রশ্ন¶
একটা 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¶
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-এর সবচেয়ে দামি ফাঁদ।
চেনা উদাহরণে বোঝা¶
ভাবো nটা ইট দিয়ে তুমি একটা আয়তক্ষেত্রাকার দেয়াল বানাতে চাও, একটাও ইট নষ্ট না করে। কত রকম মাপের (লম্বা × চওড়া) দেয়াল বানানো যায়?
- 12টা ইট দিয়ে:
1×12,2×6,3×4,4×3,6×2,12×1— প্রতিটা মাপের একটা পাশ একটা factor - লক্ষ করো —
2×6আর6×2একই দুটো সংখ্যা, শুধু ঘুরিয়ে। তাই অর্ধেক মাপ গুনে জোড়া ধরে দ্বিগুণ করলেই হয়
মানে প্রতিটা factor হলো একটা সম্ভাব্য "এক পাশের দৈর্ঘ্য", আর তারা স্বাভাবিকভাবেই জোড়ায় আসে (এক পাশ ঠিক করলে অন্য পাশ আপনিই ঠিক)। √n হলো সেই বর্গাকার দেয়ালের বাহু — তার এপারে খুঁজলেই সব জোড়া ধরা পড়ে।
ভিত্তির ধারণা¶
আগের কোন ধারণাটি লাগবে¶
সরাসরি 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 চেক না বুঝলে এখানে গোনার ভিত্তিটাই দুর্বল থাকবে।
ভেতরের অঙ্ক¶
মূল 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 পর্যন্ত যাওয়ার দরকার নেই।
ধাপে ধাপে সমাধান¶
প্রথম সরল উপায়¶
সবচেয়ে সৎ, সরাসরি ভাবনা — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা দেখি, যেটা ভাগ করে তাকে গুনি:
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-এ একদম ঠিক।
কোথায় বেশি কাজ হতে পারে¶
সমস্যা একটাই — এই loop ঘোরে পুরো n বার:
n = 1,000,000হলে 10 লক্ষ বার loop — তাও হয়তো চলে। কিন্তুn = 10¹²(এক লক্ষ কোটি) হলে 10¹² বার — কয়েক ঘণ্টা লাগবে, interview-তে নিশ্চিত Time Limit Exceeded।
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) জোড়া! একই তথ্য দু'বার খোঁজা। জোড়ার সম্পর্ক কাজে লাগালে অর্ধেকেরও কম কাজে শেষ।
আরও ভালোভাবে ভাবা¶
মূল insight — √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ (i আর n//i) গুনে নাও:
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 কমিয়ে দিই।
ভাবনার পরিবর্তন¶
মূল মোচড় এক বাক্যে: factor জোড়ায় আসে, প্রতি জোড়ার ছোট জন ≤ √n — তাই √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ গুনলেই সব factor, অর্ধেক কাজে।
ছোট্ট কিন্তু জরুরি tweak এর ভেতরে: perfect square-এ মাঝের factor (√n) নিজের জোড়া (36-এ 6×6 = 36) — তাকে দুবার গোনা যাবে না, একবার। এই −1 ভুলে গেলে perfect square-এ উত্তর ঠিক 1 বেশি আসবে।
এই "জোড়া ধরে √n পর্যন্ত" চিন্তা পরের problem-এর শিরদাঁড়া: prime check-এও আমরা একই যুক্তিতে √n পর্যন্তই ভাজক খুঁজব।
ছবিতে বোঝা¶
n = 36-এর factor জোড়াগুলো — √36 = 6-এর দু'পাশে কীভাবে আয়নার মতো সাজানো, দেখো:
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-এই থামি, এক বাক্যে:
ছোট input-এ ধাপে ধাপে¶
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 হতো।
কোড ও ব্যাখ্যা¶
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!")
কোডের প্রতিটি অংশ¶
factor গোনা positive সংখ্যার জন্যই অর্থপূর্ণ; 0 বা negative-এ 0 ফেরাই (রক্ষাকবচ)।
এই problem-এর প্রাণ। i চলে 1 থেকে √n পর্যন্ত — কিন্তু sqrt না ডেকে i * i <= n লিখছি, যাতে integer হিসাবেই থাকে আর float rounding-এর ভুল না হয়।
i ভাগ করলে (011-এর চেক), জোড়ার দুজন — i আর n // i — দুটোকেই গুনি, তাই +2।
সবচেয়ে ভোলা লাইন। 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 মিলিয়ে দেখা¶
চালালে ছাপবে:
তিনটা লাইন তিনটা 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-এর সমান উত্তর দেয়।
খরচ ও সাধারণ ভুল¶
সময়¶
O(√n) — loop চলে 1 থেকে √n পর্যন্ত, তাই প্রায় √n বার। n = 10¹² হলেও মাত্র 10⁶ ধাপ — সেকেন্ডের ভগ্নাংশ। (brute version O(n) — n = 10¹²-এ অসম্ভব ধীর।) এই O(n) → O(√n) নামানোই এই level-এর কেন্দ্রীয় শিক্ষা।
অতিরিক্ত জায়গা¶
count_factors: O(1) — শুধুcount,i; কোনো list নেই।list_factors: O(√n) (বা মোট factor সংখ্যার সমান) — কারণ factor-গুলো তালিকায় জমা হয়।
শুধু গুনতে হলে O(1) space-ই যথেষ্ট।
যে ভুলগুলো এড়াতে হবে¶
- perfect square-এ −1 ভুলে যাওয়া — এক নম্বর ফাঁদ। 36-এ 6 দুবার গোনা পড়লে উত্তর ভুল করে 10 হয়।
if i * i == n: count -= 1চাই। i <= sqrt(n)দিয়ে float-ভুল —math.sqrt(n)float দেয়, বড় n-এ rounding-এ একটা factor ফসকাতে বা বাড়তে পারে। সবসময়i * i <= n(integer) লেখো।range(1, n)দিয়ে n-কে বাদ — n নিজেও তো নিজের factor; brute-এrange(1, n+1)লাগে।+2-এর বদলে+1করা — √n পর্যন্ত খুঁজলে প্রতিবার জোড়া (i ও n//i) পাও, তাই +2; শুধু +1 করলে √n-এর ওপারের factor-গুলো বাদ পড়বে।- n = 1 ভুল হওয়া —
i=1, 1*1<=1সত্যি,1%1==0→ +2, কিন্তু1*1==1→ −1, মোট 1। ঠিক (1-এর factor শুধু নিজে)। কিন্তু hand-rolled version-এ সাবধান না হলে এটা গুলিয়ে যায়।
শেখা ও পরের অনুশীলন¶
এই ধারণার পরের অনুশীলন¶
- 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 (https://cses.fi/problemset/task/1713)। - LeetCode — Four Divisors (https://leetcode.com/problems/four-divisors/) — ঠিক 4টা divisor আছে এমন সংখ্যা খোঁজা; এই factor-জোড়া গোনার সরাসরি প্রয়োগ।
কৌশলটি মনে রাখুন¶
√n factor-pair counting — factor জোড়ায় আসে, প্রতি জোড়ার ছোট জন ≤ √n, তাই √n পর্যন্ত খুঁজে জোড়াসুদ্ধ গুনলেই সব factor। বড় শিক্ষা: O(n) loop-কে O(√n)-এ নামানোর এই "জোড়ার অপর প্রান্ত n//i দিয়ে পাওয়া যায়" কৌশলটাই এই level-এর master key — prime check, factorization সব এর সন্তান। আর perfect square-এর মাঝবিন্দু একবার গোনার সতর্কতা।
নিজেকে যাচাই করুন¶
ভবিষ্যতের আমাকে এক লাইনে: "count factors = i*i <= n loop, প্রতি n%i==0-তে +2 (i ও n//i), কিন্তু i*i==n হলে −1 (perfect square-এর মাঝ একবার)। O(n) থেকে O(√n)-এ নামার মূল মন্ত্র: জোড়ার অপর প্রান্ত n//i আপনিই পাওয়া যায়। sqrt নয়, i*i দিয়ে compare।"
আগের ধাপ → 011 — Divisibility Rules (যে n % d == 0 চেক বারবার চালাচ্ছি)। পরের ধাপ → 013 — Check Prime (এই √n loop-এ একটাও ভাজক পেলেই composite)।
ফিরে দেখা: এই 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" হিসেবে লেখা।