016 — Prime Factorization

013-এ তুমি দেখেছ একটা সংখ্যা prime কিনা। আজ আরও গভীরে — যে সংখ্যা prime নয়, তাকে prime-দের গুণফলে ভেঙে ফেলা। প্রতিটা সংখ্যার একটা অনন্য "DNA" আছে: 360 = 2³ × 3² × 5। এই DNA বের করার কৌশল পেঁয়াজের খোসা ছাড়ানোর মতো — সবচেয়ে ছোট prime দিয়ে যতবার পারো ভাগ করো, তারপর পরেরটা। একটা চমকপ্রদ ব্যাপারও দেখব — ভাগ করার সময় p prime কিনা আলাদা করে যাচাই করাই লাগে না! ধীরে যাও, শেষের if n > 1 অংশটা মন দিয়ে বুঝো — ওটাই সবচেয়ে বেশি ভোলা।

Source

• Original source: Classic exercise (related: Project Euler 3 — https://projecteuler.net/problem=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)

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।

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।

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-ও আবছা থাকবে।

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।

5. Visual explanation

360-এর খোসা ছাড়ানো ধাপে ধাপে — কোন prime কতবার, পাশে দেখো:

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 কিনা যাচাই লাগেনি!

6. Example input and output

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 হারিয়ে যায়।

7. Brute force thinking

সবচেয়ে সরল ভাবনা — 2 থেকে n পর্যন্ত প্রতিটা সংখ্যা দিয়ে যতবার পারো ভাগ করো:

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 পর্যন্ত গেলেই হতো।

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:

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-এর প্রাণ।

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 থাকত না।

12. Python solution

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!।

14. Output walkthrough

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

{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 সব ক্ষেত্রে সঠিক।

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-ও মিথ্যা, তাই {} — যা ঠিক।

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 (https://projecteuler.net/problem=3) — বিশাল সংখ্যার largest prime factor; এই √n peeling-এরই সরাসরি প্রয়োগ।

19. Pattern learned

Prime factorization via peeling — ছোট prime দিয়ে √n পর্যন্ত নিঃশেষে ভাগ করতে থাকো, শেষে n > 1 থাকলে সে-ও prime। বড় শিক্ষা: ছোট থেকে বড় ছাঁকলে composite নিয়ে আলাদা ভাবতেই হয় না (p prime কিনা check অপ্রয়োজনীয়), আর √n-এর পরে বড়জোর একটা prime বাকি — তাই if n > 1 দিয়ে তাকে ধরা। এই DNA-ই divisor count, phi, sum — সব multiplicative function-এর চাবি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "factorize = p*p <= n পর্যন্ত প্রতিটা p দিয়ে ভেতরের while-এ নিঃশেষে ভাগ ও গোনা; শেষে if n > 1 হলে সেই n-ই অবশিষ্ট বড় prime। p prime কিনা check লাগে না (ছোট আগে ছাঁকা)। if n > 1 ভুলো না — বড় prime factor ওখানেই ধরা।"

আগের ধাপ → 013 — Check Prime (যে √n trial division থেকে এল)। পরের ধাপ → 017 — Smallest Prime Factor (অনেক সংখ্যা দ্রুত factorize)। কাজে লাগবে → 024 — Number of Divisors।

ফিরে দেখা: এই 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" হিসেবে লেখা।