017 — Smallest Prime Factor

এই level-এর শেষ problem — আর এটা দুটো আগের idea-র সুন্দর মিলন: 015-এর Sieve (কাটাকাটি) আর 016-এর factorization (খোসা ছাড়ানো)। মূল চিন্তা একটাই — চালুনি চালানোর সময় প্রতিটা ঘরে শুধু "কাটা পড়েছে কিনা" (True/False) না লিখে, লিখে রাখো "প্রথম কে তোমাকে কাটল" — সেটাই তার smallest prime factor (SPF)। একবার এই তালিকা বানিয়ে রাখলে, যেকোনো সংখ্যাকে factorize করা যায় বিদ্যুৎবেগে, O(log n)-এ — খোঁজাখুঁজি নেই, সিঁড়ি ready। এই precompute-pattern competitive programming-এর মুকুটমণি; ধীরে গেঁথে নাও।

Source

• Original source: CP-Algorithms — sieve variants (smallest prime factor / linear sieve) (https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)
• Platform: CP-Algorithms
• Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
• Difficulty: Medium
• Pattern: SPF sieve
• Basic idea inherited from: 015 (Sieve of Eratosthenes)

1. Problem in simple words

একটা সংখ্যা N দেওয়া আছে। 2 থেকে N পর্যন্ত প্রতিটা সংখ্যার smallest prime factor (SPF) — মানে সবচেয়ে ছোট prime যেটা তাকে ভাগ করে — আগে থেকে বের করে রাখতে হবে।

যেমন: 12-এর SPF 2 (12 = 2×6), 15-এর SPF 3 (15 = 3×5), 7-এর SPF 7 (নিজেই prime), 35-এর SPF 5।

আর এই SPF তালিকা একবার বানালে, যেকোনো n ≤ N-কে খুব দ্রুত factorize করা যায় — বারবার spf[n] দিয়ে ভাগ করতে করতে নেমে।

2. What is the math idea?

মূল idea — sieve চালানোর সময় "প্রথম কে কাটল" লিখে রাখা। 015-এর Sieve-এ আমরা শুধু True/False রাখতাম; এখানে একটা spf[] array রাখি, যেখানে প্রতিটা সংখ্যার নিচে লেখা থাকে তাকে প্রথম কোন prime কেটেছে।

spf = [0..N]  (শুরুতে spf[i] = i ধরা — যেন সবাই নিজে prime)
i = 2 থেকে √N পর্যন্ত:
    যদি spf[i] == i (i prime, কেউ কাটেনি):
        i*i, i*i+i, ... এর জন্য:
            যদি spf[j] == j (j-কে আগে কেউ কাটেনি):
                spf[j] = i      # i-ই j-এর smallest prime factor

তারপর factorize করতে: while n > 1: p = spf[n]; গোনো; n //= p। প্রতি ধাপে n অন্তত অর্ধেক হয়, তাই O(log n) প্রতি factorization।

3. Which basic idea does this inherit from?

সরাসরি 015 (Sieve of Eratosthenes) থেকে — কাঠামো প্রায় হুবহু এক, শুধু ঘরে কী লিখছি সেটা বদলেছে।

015:  is_prime[j] = False    -> শুধু "কাটা পড়েছে" (হ্যাঁ/না)
017:  spf[j] = i             -> "কে প্রথম কাটল" (কোন prime)

015-এ আমরা ফেলে দিতাম তথ্য — কে কাটল সেটা ভুলে যেতাম, শুধু "কাটা/অকাটা" রাখতাম। 017-এ সেই হারিয়ে-যাওয়া তথ্যটাই ধরে রাখি — আর সেটুকুই factorization-কে বিদ্যুৎগতি দেয়। সাথে 016-এর peeling idea-ও মিশছে: factorize করার সময় ছোট prime দিয়ে নামি, শুধু এবার "কোন prime" খুঁজতে হয় না — spf[n] সরাসরি বলে দেয়। তাই 015 আর 016 দুটোই না বুঝলে এই মিলনটা ধরা কঠিন।

4. Real-life analogy

ভাবো একটা বড় ক্লাসে নাম-ডাকা (roll call), কিন্তু একটু অন্যভাবে। শিক্ষক prime-দের একে একে ডাকেন, আর প্রতিটা prime তার নামতার ছাত্রদের গায়ে নিজের স্ট্যাম্প মারে — কিন্তু নিয়ম হলো, যার গায়ে আগে স্ট্যাম্প পড়েনি শুধু তাকেই।

• 2 প্রথমে সব জোড় সংখ্যার (4, 6, 8...) গায়ে "2" স্ট্যাম্প মারে
• 3 এসে যাদের গায়ে এখনো স্ট্যাম্প নেই (9, 15, 21...) তাদের "3" মারে — 6, 12 আগেই 2-এর স্ট্যাম্প পেয়েছে, তাই বাদ
• ফলে প্রতিটা সংখ্যার গায়ে থাকে সবচেয়ে ছোট prime-এর স্ট্যাম্প (কারণ ছোট prime আগে ডাক পায়)

12-এর গায়ে "2" (প্রথম স্ট্যাম্প), 15-এর গায়ে "3"। এই স্ট্যাম্প-ই SPF। আর কাউকে factorize করতে হলে — গায়ের স্ট্যাম্প দেখো, ভাগ করো, আবার দেখো — সিঁড়ি বেয়ে নামার মতো।

5. Visual explanation

2 থেকে 12-এ SPF সাজানো হচ্ছে — ছোট prime আগে স্ট্যাম্প মারে বলে প্রতিটা পায় তার smallest:

শুরুতে spf[i] = i (সবাই নিজে):
 i  :  2  3  4  5  6  7  8  9 10 11 12
spf :  2  3  4  5  6  7  8  9 10 11 12

i=2 (spf[2]==2, prime): 4,6,8,10,12-এ "2" বসাও (যাদের spf এখনো নিজে):
spf :  2  3 [2] 5 [2] 7 [2] 9 [2] 11 [2]

i=3 (spf[3]==3, prime): 9 থেকে — 9-এ "3"; 12 আগেই 2 পেয়েছে, বাদ:
spf :  2  3  2  5  2  7  2 [3] 2 11  2

i=4: spf[4]==2 ≠ 4 -> 4 prime নয়, skip। i=5: 5*5=25>12 -> শেষ।

চূড়ান্ত SPF:  12->2, 9->3, 15 হলে ->3, prime হলে নিজে

এবার SPF দিয়ে 12 factorize — সিঁড়ি বেয়ে নামা:

n=12: spf[12]=2 -> ভাগ -> n=6   (2 গোনো)
n=6 : spf[6]=2  -> ভাগ -> n=3   (2 গোনো)
n=3 : spf[3]=3  -> ভাগ -> n=1   (3 গোনো)
n=1 : থামো  ->  12 = 2² × 3

6. Example input and output

build_spf(N) তৈরির পর:
-----------------------------------------
spf[12] -> 2      (12 = 2×6)
spf[15] -> 3      (15 = 3×5)
spf[7]  -> 7      (prime — নিজে)
spf[35] -> 5      (35 = 5×7)
spf[2]  -> 2

factorize(n) (spf ব্যবহার করে):
factorize(12)  -> {2: 2, 3: 1}
factorize(360) -> {2: 3, 3: 2, 5: 1}
factorize(97)  -> {97: 1}        (prime, spf[97]=97)

মূল কথা: SPF তালিকা একবার বানালে (O(N log log N)), তারপর প্রতিটা factorize মাত্র O(log n) — বহু সংখ্যা factorize করতে হলে এটাই সেরা। (একটামাত্র সংখ্যা হলে 016-এর সরাসরি peeling-ই যথেষ্ট, sieve বানানোর দরকার নেই।)

7. Brute force thinking

"Brute force" এখানে — প্রতিটা সংখ্যার SPF আলাদা করে খুঁজে বের করা, কোনো precompute ছাড়া:

def smallest_prime_factor(n):
    if n % 2 == 0:
        return 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return i           # প্রথম ভাজকই smallest prime factor
        i += 2
    return n                   # কেউ না পেলে n নিজেই prime

def factorize_no_sieve(n):
    factors = {}
    while n > 1:
        p = smallest_prime_factor(n)
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    return factors

এটা ঠিক উত্তর দেয় — প্রতিবার √n trial division করে smallest factor খুঁজি (এটা আসলে 016-এর peeling-ই)। একটা-দুটো সংখ্যার জন্য একদম যথেষ্ট।

8. Why brute force may be slow

সমস্যা তখন, যখন অনেক সংখ্যা factorize করতে হয় (যেমন 1 থেকে N সবার):

• প্রতিটা সংখ্যার জন্য আলাদা √n খোঁজা — N সংখ্যার জন্য মোট ≈ O(N√N)। N = 10⁶ হলে ~10⁹ কাজ, ধীর।

1 থেকে N সবাইকে factorize করতে হলে:
  per-number trial : O(N√N) ≈ 10^9       -> ধীর
  SPF sieve        : O(N log log N) বানানো + O(log n) প্রতিটা  -> অনেক দ্রুত

কোথায় অপচয়? একই কাজ (ছোট factor খোঁজা) বারবার করছি — 12, 24, 36 সবার জন্য আলাদা করে "2 কি ভাগ করে?" আবিষ্কার করছি। SPF sieve একবার সবার smallest factor লিখে রাখে; তারপর প্রতিবার খোঁজা নয়, শুধু পড়া (spf[n])। এই "একবার precompute, পরে শুধু lookup" সেই 015-এর কারখানা-দর্শনেরই সম্প্রসারণ।

9. Better thinking

মূল insight — sieve-এর সময় smallest prime factor লিখে রাখো, পরে শুধু lookup করে নামো:

def build_spf(N):
    spf = list(range(N + 1))           # spf[i] = i (শুরুতে সবাই নিজে)
    i = 2
    while i * i <= N:
        if spf[i] == i:                # i prime (কেউ কাটেনি)
            for j in range(i * i, N + 1, i):
                if spf[j] == j:        # j-কে আগে কেউ কাটেনি
                    spf[j] = i         # i-ই j-এর smallest prime factor
        i += 1
    return spf

def factorize(n, spf):
    factors = {}
    while n > 1:
        p = spf[n]                     # খুঁজতে হয় না — সরাসরি পড়ি
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    return factors

দুটো জরুরি সূক্ষ্মতা: (১) if spf[j] == j — শুধু তখনই লিখি যখন j-কে আগে কেউ কাটেনি, যাতে সবচেয়ে ছোট prime-ই থেকে যায় (ছোট prime আগে চলে বলে); (২) factorize-এ p = spf[n] সরাসরি, কোনো trial division নেই — তাই বিদ্যুৎগতি।

10. Thinking tweak

মূল মোচড় এক বাক্যে: 015-এর চালুনিতে True/False-এর বদলে "প্রথম কে কাটল" লিখে রাখলে, প্রতিটা সংখ্যার smallest prime factor হাতে থাকে — আর factorization আর খোঁজা নয়, শুধু spf ধরে সিঁড়ি বেয়ে নামা।

এর ভেতরে দুটো "আহা":

• ছোট prime আগে কাটে বলেই smallest: sieve-এ i বাড়ে 2, 3, 5... ক্রমে, তাই কোনো সংখ্যার গায়ে প্রথম যে stamp পড়ে সেটাই সবচেয়ে ছোট prime। if spf[j] == j শর্তটা এই "প্রথমটাই থাকুক" নিশ্চিত করে।
• lookup > search: একবার তথ্য জমিয়ে রাখলে (precompute), পরে প্রতিবার নতুন করে হিসাব না করে শুধু পড়ে নেওয়া — এই tradeoff (একটু বেশি স্মৃতি ও একবারের সময়, বিনিময়ে বহু দ্রুত query) competitive programming-এর কেন্দ্রীয় কৌশল।

11. Step-by-step dry run

দুই ভাগ। প্রথমে build_spf(12)-এর কাটাকাটি (i*i <= 12 মানে i = 2, 3):

i	spf[i] == i? (prime?)	i²	কোন j-তে spf[j]=i বসে (যদি spf[j]==j)
2	2==2 ✓	4	4, 6, 8, 10, 12 → সবার spf = 2
3	3==3 ✓	9	9 → spf=3; 12 আগেই 2 পেয়েছে (spf[12]≠12), বাদ

i=4-এ spf[4]=2 ≠ 4 → skip; i=5-এ 25 > 12 → শেষ। ফলাফল: spf[12]=2, spf[9]=3, prime-রা নিজে।

এবার সেই spf দিয়ে factorize(12, spf):

n (শুরুতে)	p = spf[n]	ভেতরের while	n হয়ে যায়	factors
12	spf[12]=2	12→6 (একবার)	6	{2: 1}
6	spf[6]=2	6→3 (একবার)	3	{2: 2}
3	spf[3]=3	3→1 (একবার)	1	{2: 2, 3: 1}

n=1, loop থামল। {2: 2, 3: 1} = 12 = 2² × 3। লক্ষ করো — কোনো ভাজক "খুঁজতে" হয়নি, প্রতিবার spf[n] সরাসরি বলে দিয়েছে; প্রতি ধাপে n অন্তত অর্ধেক — তাই দ্রুত।

12. Python solution

def build_spf(N):
    """2..N প্রতিটা সংখ্যার smallest prime factor — O(N log log N)।"""
    spf = list(range(N + 1))           # spf[i] = i (সবাই শুরুতে নিজে)
    i = 2
    while i * i <= N:
        if spf[i] == i:                # i prime
            for j in range(i * i, N + 1, i):
                if spf[j] == j:        # আগে কেউ কাটেনি -> এই i-ই smallest
                    spf[j] = i
        i += 1
    return spf


def factorize(n, spf):
    """spf array দিয়ে n factorize — প্রতিবার O(log n)।"""
    factors = {}
    while n > 1:
        p = spf[n]                     # খোঁজা নয়, সরাসরি পড়া
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    return factors


def factorize_check(n):
    """স্বাধীন peeling (016-এর মতো) — যাচাইয়ের জন্য, sieve ছাড়া।"""
    factors = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
        p += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors


# --- ছোট test গুলো (সব pass করা উচিত) ---
N = 1000
spf = build_spf(N)

assert spf[12] == 2
assert spf[15] == 3
assert spf[7] == 7          # prime -> নিজে
assert spf[35] == 5
assert spf[2] == 2
assert spf[97] == 97        # prime

# spf দিয়ে factorize আর স্বাধীন peeling — সব n-এ মেলে কিনা (সোনার যাচাই)
for n in range(2, N + 1):
    assert factorize(n, spf) == factorize_check(n)

# prime হলে spf[p] == p, composite হলে spf[c] < c
for n in range(2, 100):
    is_prime = factorize_check(n) == {n: 1}
    assert (spf[n] == n) == is_prime

print(spf[12])              # 2
print(spf[35])             # 5
print(factorize(360, spf)) # {2: 3, 3: 2, 5: 1}
print("সব test pass!")

13. Line-by-line explanation

    spf = list(range(N + 1))

spf[i] = i দিয়ে শুরু — মানে "ধরে নিলাম প্রত্যেকে নিজের smallest factor" (prime হলে এটাই সত্যি থাকবে; composite হলে পরে ছোট prime বসবে)। N + 1 ঘর যাতে index N থাকে।

    while i * i <= N:
        if spf[i] == i:

বাইরের loop √N পর্যন্ত (015-এর মতো)। if spf[i] == i মানে i-কে কেউ কাটেনি — অর্থাৎ i prime; তবেই তার গুণিতকে stamp মারার মানে আছে।

            for j in range(i * i, N + 1, i):
                if spf[j] == j:
                    spf[j] = i

এই problem-এর হৃদয়। i-এর গুণিতক (i² থেকে) ঘুরি; কিন্তু if spf[j] == j — শুধু তখনই i বসাই যখন j-কে আগে কেউ কাটেনি। এই শর্তই নিশ্চিত করে সবচেয়ে ছোট prime থেকে যায় (বড় prime এসে আর overwrite করতে পারে না)।

def factorize(n, spf):
    while n > 1:
        p = spf[n]
        while n % p == 0:
            ...
            n //= p

factorize — p = spf[n] সরাসরি smallest prime দেয় (খোঁজা নেই), সেটা দিয়ে নিঃশেষে ভাগ ও গোনা, তারপর আবার নতুন spf[n]। প্রতি ধাপে n ছোট হয়, n=1-এ থামে।

for n in range(2, N+1) loop — spf-ভিত্তিক factorize-কে স্বাধীন peeling-এর সাথে 999টা সংখ্যায় মিলিয়ে যাচাই; দ্বিতীয় loop prime চেনা (spf[n]==n) নিশ্চিত করে। সব মিললে সব test pass!।

14. Output walkthrough

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

2
5
{2: 3, 3: 2, 5: 1}
সব test pass!

প্রথম দুই লাইন spf[12] → 2 আর spf[35] → 5 (smallest prime factor)। তৃতীয় লাইন factorize(360, spf) → {2:3, 3:2, 5:1} (= 2³×3²×5, spf ধরে নেমে)। তার আগে সব assert — নির্দিষ্ট spf মান, 2..1000 জুড়ে spf-factorize বনাম স্বাধীন peeling-এর মিল, আর prime-চেনা — চুপচাপ pass করেছে। শেষ লাইন সব test pass! মানে SPF sieve ও তা দিয়ে factorization সব ক্ষেত্রে সঠিক।

15. Time complexity

• build_spf(N): O(N log log N) — 015-এর Sieve-এর মতোই কাটাকাটি, শুধু ঘরে i লিখছি।
• প্রতিটা factorize(n, spf): O(log n) — প্রতি ধাপে n অন্তত অর্ধেক হয় (smallest prime ≥ 2 দিয়ে ভাগ), তাই বড়জোর log₂ n ধাপ। কোনো trial division নেই।

মানে একবার O(N log log N) খরচ করে তালিকা বানালে, এরপর প্রতিটা query প্রায় বিনামূল্যে — বহু factorization-এ বিশাল সাশ্রয়।

16. Space complexity

O(N) — spf array-তে N+1 ঘর (প্রতিটা ঘরে একটা integer, 015-এর boolean-এর চেয়ে সামান্য বেশি)। এটাই precompute-এর দাম: একটু বেশি স্মৃতি ও একবারের সময়, বিনিময়ে O(log n) factorization — classic time/space tradeoff। বিশাল N-এ স্মৃতি সীমাবদ্ধতা হতে পারে।

17. Common mistakes

1. if spf[j] == j শর্ত ভুলে যাওয়া — এক নম্বর ফাঁদ। শর্ত ছাড়া বড় prime এসে ছোট prime-এর stamp overwrite করতে পারে, তখন spf আর "smallest" থাকে না। শুধু প্রথমবার (যখন spf[j]==j) লেখা জরুরি।
2. spf[i] = list(range(N+1)) ভুল init — শুরুতে spf[i] = i হওয়া চাই (list(range(N+1))), যাতে prime-রা স্বাভাবিকভাবে নিজেকে ধরে রাখে; 0/False দিয়ে শুরু করলে prime চেনা ভেঙে যায়।
3. একটা মাত্র সংখ্যার জন্য sieve বানানো — শুধু একটা n factorize করতে হলে SPF sieve অপচয় (O(N) স্মৃতি+সময়); তখন 016-এর সরাসরি O(√n) peeling-ই ভালো। SPF-এর লাভ বহু query-তে।
4. factorize-এ ভেতরের while বাদ — while n % p == 0 ছাড়া একই prime-এর একাধিক power (যেমন 2³) ঠিকমতো গোনা হবে না; আর n-ও কমবে না।
5. i*i / √N সীমা ভুলে N পর্যন্ত চালানো — কাজ করে কিন্তু অপচয়; 015-এর মতোই √N যথেষ্ট।

18. Harder problems that inherit this idea

• 024 — Number of Divisors / 025 — Sum of Divisors (এই repo) — বহু সংখ্যার divisor count/sum দরকার হলে SPF দিয়ে দ্রুত factorize করে exponent থেকে formula।
• 023 — Euler Phi (এই repo) — একই — SPF দিয়ে দ্রুত factorization করে ∏(1 - 1/p) প্রয়োগ; বিশেষত অনেক n-এর জন্য phi লাগলে।
• CP-Algorithms — Linear Sieve (https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html) — SPF-এর আরও উন্নত রূপ (প্রতিটা composite ঠিক একবার কাটা, O(N)); এই idea-রই পরের ধাপ।

19. Pattern learned

SPF sieve — চালুনিতে "কে প্রথম কাটল" লিখে রাখো, পরে lookup করে O(log n) factorize। বড় শিক্ষা: 015-এ ফেলে দেওয়া তথ্য (কে কাটল) ধরে রাখলেই factorization খোঁজা থেকে পড়ায় নেমে আসে; আর "একবার precompute, বহু query free" — এই time/space tradeoff বহু সংখ্যায় কাজ করার মূল কৌশল। এটা 015 (sieve) আর 016 (peeling)-এর সুন্দর সংশ্লেষ।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "SPF sieve = spf = list(range(N+1)), 015-এর মতো কাটো কিন্তু if spf[j]==j: spf[j]=i (প্রথমটাই = smallest)। factorize: while n>1: p=spf[n]; নিঃশেষে ভাগ ও গোনা — O(log n)। একটা সংখ্যা হলে 016 যথেষ্ট; বহু সংখ্যা হলে SPF।"

আগের ধাপ → 015 — Sieve of Eratosthenes (যে চালুনিতে এবার factor লিখছি)। সাথে মিশছে → 016 — Prime Factorization (peeling idea)। কাজে লাগবে → 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" হিসেবে লেখা।