137 — Sieve Variants

Level 1-এ basic sieve (Eratosthenes) শিখেছিলে — সব prime খুঁজতে। এই note-এ সেই ছাঁকনির দুটো শক্তিশালী রূপ: SPF (smallest prime factor) sieve আর linear sieve — যা শুধু prime নয়, প্রতিটা সংখ্যার দ্রুত factorization-ও দেয়। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — তবে sieve-চিন্তা interview-তেও মাঝে মাঝে কাজে লাগে (precompute pattern)। 015 (basic sieve) ঝালাই থাকলে এটা স্বাভাবিক পরের ধাপ। এটা sieve জোড়ার (137 → 138) প্রথম।

Source

• Original source: CP-Algorithms — Linear Sieve
• Platform: CP-Algorithms — https://cp-algorithms.com/algebra/prime-sieve-linear.html
• Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
• Difficulty: Medium
• Pattern: SPF / linear sieve
• Basic idea inherited from: 015 (Sieve of Eratosthenes)

1. Problem in simple words

1 থেকে N পর্যন্ত সব সংখ্যা নিয়ে কাজ — কিন্তু এবার শুধু "কোনগুলো prime" নয়, আরও বেশি:

• SPF sieve: প্রতিটা সংখ্যার smallest prime factor (সবচেয়ে ছোট prime গুণনীয়ক) টুকে রাখা। এটা থাকলে যেকোনো সংখ্যার full factorization O(log n)-এ — শুধু spf ধরে ধরে ভাগ।
• Linear sieve: Eratosthenes-এর একটা পরিমার্জন যেখানে প্রতিটা composite ঠিক একবার কাটা পড়ে (এক প্রস্থে, O(N)), আর একই pass-এ prime তালিকা + SPF (চাইলে φ বা μ-ও) বানানো যায়।

মূল লক্ষ্য — একবার precompute করে নিয়ে, তারপর হাজার হাজার query-তে দ্রুত factorization বা prime-চেক। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু "একবার বানিয়ে বারবার ব্যবহার" — precompute-চিন্তা সর্বত্র কাজে লাগে।

2. What is the math idea?

মূল idea — ছাঁকনিতে শুধু "prime কি না" নয়, "কে প্রথম কাটল" সেটাও মনে রাখা।

• Eratosthenes (015): প্রতিটা prime p-এর গুণিতক (p², p²+p, ...) কেটে দাও — যা টিকে থাকে তারা prime।
• SPF: কাটার সময় প্রতিটা সংখ্যার পাশে লিখে রাখো কোন প্রথম (ক্ষুদ্রতম) prime তাকে কাটল। তারপর n-কে factorize করতে: spf[n] দিয়ে ভাগ, বাকিটার আবার spf দিয়ে ভাগ... — প্রতি ভাগে অন্তত 2 গুণ ছোট হয়, তাই O(log n)।
• Linear sieve: সাধারণ sieve-এ 12 কাটা পড়ে 2 আর 3 দুজনের হাতে (দ্বৈত কাজ)। linear sieve-এর নিয়ম: প্রতিটা composite-কে শুধু তার smallest prime factor দিয়েই কাটো — তাই প্রতিটা সংখ্যা ঠিক একবার ছোঁয়া হয়, মোট O(N)।

এই level CP-leaning হলেও মূল সুর সরল — "কাটার সময় কে কাটল মনে রাখলে, পরে factorization বিনামূল্যে।"

3. Which basic idea does this inherit from?

সরাসরি 015 (Sieve of Eratosthenes)। দুটো variant-ই Eratosthenes-এর "গুণিতক কেটে দাও" কাঠামোর উপর — SPF শুধু কাটার সময় "কে কাটল" টুকে রাখে, linear sieve কাটার নিয়মটা শক্ত করে (প্রতিটা একবার)।

পেছনে prime factorization-এর ধারণা (Level 1)। আর এর উপরে দাঁড়াবে 138 (Segmented Sieve) — যখন range [L, R] বিশাল (R = 10¹²) কিন্তু পুরো array রাখা অসম্ভব, তখন একই Eratosthenes-কে window-তে নামানো। README-র recommended order: 137 → 138। আর SPF/φ/μ-এর multiplicative-চিন্তা 128, 129-এর সাথে মেলে।

4. Real-life analogy

ভাবো একটা বিশাল লাইব্রেরিতে বই সাজানো (1 থেকে N নম্বর দেওয়া)। তুমি একদল লাইব্রেরিয়ান (prime-রা) দিয়ে বই "চিহ্নিত" করাচ্ছ — 2-নম্বর লাইব্রেরিয়ান সব জোড়-নম্বর বই ছোঁয়, 3-নম্বর সব 3-এর গুণিতক, ইত্যাদি।

• সাধারণ sieve (015): একটা বই (যেমন 12) একাধিক লাইব্রেরিয়ান (2 আর 3) আলাদা করে ছোঁয় — দ্বৈত কাজ, অপচয়।
• SPF: প্রতিটা বইয়ের গায়ে স্টিকার — "তোমাকে প্রথম কে ছুঁয়েছিল" (ক্ষুদ্রতম prime)। তখন যেকোনো বইয়ের পুরো "মালিকানা-শৃঙ্খল" (factorization) দ্রুত পড়ে নেওয়া যায়।
• linear sieve: কড়া নিয়ম — প্রতিটা বই ঠিক একজন নির্দিষ্ট লাইব্রেরিয়ান (তার ক্ষুদ্রতম prime) ছোঁবে, কেউ দুবার নয়। তাই মোট ছোঁয়ার সংখ্যা = বইয়ের সংখ্যা (O(N)), কোনো অপচয় নেই।

স্টিকার (SPF) থাকলে পরে কোনো বইয়ের factorization জিজ্ঞেস করলে সঙ্গে সঙ্গে উত্তর — পুরো লাইব্রেরি আবার চষতে হয় না।

5. Visual explanation

SPF sieve দিয়ে 60-এর factorization — আগে spf array, তারপর ভাগ:

spf[i] = i-এর smallest prime factor (Eratosthenes-এর সময় টোকা):
  i  : 2  3  4  5  6  7  8  9 10 ... 60
  spf: 2  3  2  5  2  7  2  3  2 ...  2     (60-এর spf = 2)

60-এর factorization, spf ধরে ধরে ভাগ:
  n = 60,  spf[60] = 2  -> factor 2,  n = 30
  n = 30,  spf[30] = 2  -> factor 2,  n = 15
  n = 15,  spf[15] = 3  -> factor 3,  n =  5
  n =  5,  spf[5]  = 5  -> factor 5,  n =  1
  factorization: [2, 2, 3, 5]   ✓  (মোটে 4 ভাগ, √60 trial নয়)

linear sieve — কেন O(N): প্রতিটা composite শুধু তার spf দিয়ে কাটে
  12 কাটে শুধু 2 (2×6)-এর হাতে, 3-এর হাতে নয় -> একবারই ছোঁয়া

লক্ষ করো — SPF থাকায় 60-এর factorization মাত্র 4টা ভাগে হলো (প্রতিবার অন্তত অর্ধেক ছোট), trial division-এর √60 ≈ 8 ধাপ নয়। আর linear sieve প্রতিটা সংখ্যা একবার ছুঁয়ে O(N)।

6. Example input and output

SPF sieve (N = 20), spf array:
  i  : 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
  spf: 1  2  3  2  5  2  7  2  3  2 11  2 13  2  3  2 17  2 19  2

factorize(n) — spf ধরে:
  60   ->  [2, 2, 3, 5]
  100  ->  [2, 2, 5, 5]
  97   ->  [97]            (prime: spf[97] = 97)
  1    ->  []

linear sieve (N = 20), primes list:
  [2, 3, 5, 7, 11, 13, 17, 19]   (8টা prime 20-এর নিচে)

is_prime(n) via spf:  spf[n] == n  (n > 1 হলে) -> prime
  spf[13] == 13 -> True;   spf[12] = 2 ≠ 12 -> False

খেয়াল করো: spf[n] == n মানে n prime (নিজের ক্ষুদ্রতম prime factor নিজেই)। edge case: spf[1] = 1 (factorization খালি)। linear sieve একই pass-এ prime তালিকা + spf দেয়। প্রতিটা সংখ্যার factorization spf দিয়ে O(log n)-এ।

7. Brute force thinking

precompute ছাড়া — প্রতিটা সংখ্যা আলাদা করে trial division-এ factorize (134-এর মতো):

def factorize_trial(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

একটা সংখ্যার জন্য নিখুঁত — O(√n)। আমরা SPF-factorization এই trial division-এর সাথে মিলিয়ে যাচাই করব। কিন্তু অনেক সংখ্যা factorize করতে হলে এটা ধীর — সেখানেই SPF sieve জেতে।

8. Why brute force may be slow

একটা সংখ্যায় O(√n) ঠিক আছে; সমস্যা অনেক query-তে:

একটা factorize:           O(√n) — ঠিক আছে
Q টা query (Q ~ 10⁶), প্রতিটা ~10⁶:  Q × √n = 10⁶ × 10³ = 10⁹ — ধীর
SPF sieve একবার (O(N)) + প্রতি query O(log n):  precompute 10⁶, তারপর প্রতিটা ~20 ধাপ

CP-তে প্রায়ই হাজার হাজার সংখ্যার factorization বা prime-চেক দরকার — প্রতিবার trial division করা অপচয়। SPF sieve একবার O(N)/O(N log log N)-এ বানিয়ে নিলে, তারপর প্রতিটা factorization O(log n) — বিশাল সাশ্রয়। আর linear sieve O(N) (Eratosthenes-এর O(N log log N)-এর চেয়েও কম)।

9. Better thinking

মূল insight — একবার ছাঁকনি চালিয়ে SPF টুকে রাখো; তারপর সব factorization/prime-চেক বিনামূল্যে। দুই পদ্ধতি:

SPF sieve (Eratosthenes-ভিত্তিক):

1. spf[i] = i সবার জন্য শুরু (নিজের ক্ষুদ্রতম prime এখনো জানা নেই)
2. i = 2 থেকে √N: যদি spf[i] == i (i prime):
     j = i² থেকে N, ধাপ i: যদি spf[j] এখনো j (কাটা হয়নি): spf[j] = i
3. factorize(n): যতক্ষণ n > 1: factor = spf[n], n //= spf[n]

Linear sieve (O(N)):

1. primes = []  (খালি)
2. i = 2 থেকে N:
     যদি spf[i] == 0:  i prime, primes-এ যোগ, spf[i] = i
     প্রতিটা prime p ≤ spf[i] আর i·p ≤ N: spf[i·p] = p; যদি p == spf[i]: break

linear sieve-এর break নিয়মটাই নিশ্চিত করে প্রতিটা composite ঠিক একবার (তার smallest prime দিয়ে) কাটে — তাই O(N)। SPF থাকলে factorization O(log n) (প্রতি ভাগে ≥ 2 গুণ ছোট)।

10. Thinking tweak

আসল "আহা" মুহূর্ত: ছাঁকনিতে কাটার সময় শুধু "কাটা পড়ল" না লিখে "কে কাটল" (ক্ষুদ্রতম prime) লিখলে, factorization আর আলাদা করে করতে হয় না — array lookup-এ পাওয়া যায়।

trial division প্রতিবার শূন্য থেকে factor খুঁজছিল; tweak হলো — একবার sieve-এ SPF টুকে নাও, তখন প্রতিটা factorization শুধু spf ধরে ভাগ (O(log n))। দ্বিতীয় tweak: প্রতিটা composite-কে শুধু তার smallest prime দিয়ে কাটার নিয়ম মানলে (linear sieve) দ্বৈত-কাটা বন্ধ হয়, O(N log log N) → O(N)। আর bonus: একই linear pass-এ multiplicative function (φ, μ) বানানো যায় — 128, 129-এর সাথে মেলে।

11. Step-by-step dry run

SPF sieve বানানো (N = 12), শুরুতে spf[i] = i:

ধাপ	i	spf[i] == i? (prime?)	কী কাটল	spf array (2..12)
শুরু	—	—	—	[2,3,4,5,6,7,8,9,10,11,12]
i = 2	2	হ্যাঁ	4,6,8,10,12 → spf = 2 (যদি এখনো নিজে)	[2,3,2,5,2,7,2,9,2,11,2]
i = 3	3	হ্যাঁ	9 → spf = 3 (6,12 আগেই 2-তে কাটা)	[2,3,2,5,2,7,2,3,2,11,2]
i = 4	4	না (spf[4]=2)	skip	(অপরিবর্তিত)
...	...	...	(i² > 12 হলে থামে)	চূড়ান্ত spf

চূড়ান্ত spf[2..12] = [2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2]।

এবার factorize(12):

step	n	spf[n]	factor	নতুন n
1	12	2	2	6
2	6	2	2	3
3	3	3	3	1

factorization: [2, 2, 3] ✓ (12 = 2²·3)। লক্ষ করো — মাত্র 3টা ভাগ, প্রতিবার spf array থেকে সরাসরি।

12. Python solution

def build_spf(N):
    """smallest prime factor sieve, O(N log log N)। spf[i] = i-এর ক্ষুদ্রতম prime factor।"""
    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:               # এখনো কাটা হয়নি
                    spf[j] = i
        i += 1
    return spf


def factorize_spf(n, spf):
    """spf array দিয়ে n-এর factorization, O(log n)।"""
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors


def linear_sieve(N):
    """O(N) sieve — primes তালিকা আর spf একসাথে।"""
    spf = [0] * (N + 1)
    primes = []
    for i in range(2, N + 1):
        if spf[i] == 0:                       # i prime
            spf[i] = i
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > N:
                break
            spf[i * p] = p                    # i·p-কে p (তার smallest prime) দিয়ে কাটি
    return primes, spf


# --- ছোট test গুলো (সব pass করা উচিত) ---
def factorize_trial(n):
    factors, d = [], 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d); n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

N = 5000
spf = build_spf(N)

# SPF-factorize বনাম trial division — 2..N সব মেলাও
for n in range(2, N + 1):
    assert factorize_spf(n, spf) == factorize_trial(n), f"factorize({n}) অমিল"

# spf[n] == n  ঠিক তখনই যখন n prime
def is_prime_trial(n):
    if n < 2: return False
    d = 2
    while d * d <= n:
        if n % d == 0: return False
        d += 1
    return True
for n in range(2, N + 1):
    assert (spf[n] == n) == is_prime_trial(n), f"prime-চেক {n} অমিল"

# linear sieve — build_spf-এর সাথে spf মেলাও, primes তালিকা যাচাই
primes_lin, spf_lin = linear_sieve(N)
for n in range(2, N + 1):
    assert spf_lin[n] == spf[n], f"linear spf {n} অমিল"
assert primes_lin == [n for n in range(2, N + 1) if is_prime_trial(n)]

# নির্দিষ্ট factorization
assert factorize_spf(60, spf) == [2, 2, 3, 5]
assert factorize_spf(100, spf) == [2, 2, 5, 5]
assert factorize_spf(97, spf) == [97]
assert factorize_spf(1, spf) == []

# prime গোনা: 100-এর নিচে 25টা
assert len([p for p in primes_lin if p < 100]) == 25

print(factorize_spf(60, spf))            # [2, 2, 3, 5]
print(spf[97] == 97)                      # True (prime)
print(linear_sieve(20)[0])               # [2, 3, 5, 7, 11, 13, 17, 19]
print("সব test pass!")

13. Line-by-line explanation

def build_spf(N):
    spf = list(range(N + 1))
    i = 2
    while i * i <= N:
        if spf[i] == i:
            for j in range(i * i, N + 1, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1
    return spf

spf[i] = i দিয়ে শুরু (এখনো কাটা হয়নি)। spf[i] == i মানে i prime (কেউ কাটেনি)। তখন i²থেকে i-এর গুণিতক কাটি — কিন্তু শুধু যদি spf[j] == j (এখনো কাটা হয়নি), যাতে ক্ষুদ্রতম prime-ই থাকে (পরে বড় prime overwrite না করে)।

def factorize_spf(n, spf):
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]

spf[n] হলো n-এর ক্ষুদ্রতম prime factor — সেটা যোগ করি, n-কে তা দিয়ে ভাগ, আবার। প্রতি ভাগে n অন্তত অর্ধেক, তাই O(log n)।

def linear_sieve(N):
    spf = [0] * (N + 1)
    primes = []
    for i in range(2, N + 1):
        if spf[i] == 0:
            spf[i] = i; primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > N:
                break
            spf[i * p] = p

প্রতিটা i-এর জন্য: spf[i] == 0 হলে i prime। তারপর প্রতিটা prime p (≤ spf[i] পর্যন্ত) দিয়ে i·p-কে কাটি, spf[i·p] = p। p > spf[i] হলে break — এটাই নিশ্চিত করে প্রতিটা composite ঠিক একবার (তার smallest prime দিয়ে) কাটে, তাই O(N)।

বাকি test অংশে SPF-factorize বনাম trial (2..5000), spf[n]==n ⟺ prime, linear sieve-এর spf ও primes মিল, আর নির্দিষ্ট factorization সব যাচাই হয়। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

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

[2, 2, 3, 5]
True
[2, 3, 5, 7, 11, 13, 17, 19]
সব test pass!

factorize_spf(60, spf) → [2, 2, 3, 5] (60 = 2²·3·5, section 5-এর সাথে মিল)। spf[97] == 97 → True (97 prime, ক্ষুদ্রতম factor নিজেই)। linear_sieve(20)[0] → 20-এর নিচের 8টা prime। তার আগে 2..5000-এ SPF বনাম trial, prime-চেক, ও linear sieve-এর মিল সব assert pass — তাই সব test pass!।

15. Time complexity

build_spf: O(N log log N) — Eratosthenes-এর মতোই। linear_sieve: O(N) — প্রতিটা সংখ্যা ঠিক একবার ছোঁয়া (এর সৌন্দর্য)। factorize_spf: O(log n) প্রতি query — প্রতি ভাগে n ≥ 2 গুণ ছোট। তাই precompute একবার, তারপর Q query-তে মোট O(N + Q log n) — trial division-এর O(Q√n)-এর তুলনায় বিশাল লাফ (অনেক query-তে)।

16. Space complexity

O(N) — spf array (N+1 আকার), আর linear sieve-এ primes তালিকা (~N/ln N আকার)। CP-তে N যদি 10⁶-10⁷, এই array memory-তে রাখা যায়; তার বেশি (যেমন range 10¹²) হলে পুরো array অসম্ভব — তখন segmented sieve (138)। এটাই দুই note-এর সংযোগ।

17. Common mistakes

1. SPF-এ ক্ষুদ্রতম prime overwrite করে ফেলা — if spf[j] == j চেক না রাখলে বড় prime ছোট prime-কে overwrite করতে পারে; তখন spf আর "smallest" থাকে না, factorization ভুল।
2. linear sieve-এর break নিয়ম ভুল — if p > spf[i]: break (বা i % p == 0 সমতুল্য) না রাখলে প্রতিটা composite একাধিকবার কাটে, O(N) ভেঙে যায় ও spf ভুল হয়।
3. i² থেকে শুরু না করা (Eratosthenes-এ) — i-এর গুণিতক i² থেকে শুরু (ছোট গুণিতক আগের prime-এ কাটা); 2i থেকে শুরু করলেও ভুল হয় না কিন্তু অপচয়।
4. spf[1], spf[0] ভুল ধরা — 0, 1-এর prime factor নেই; factorize_spf-এ n > 1 শর্ত এটা সামলায় (1-এ লুপ চলে না, খালি list)।
5. বড় N-এ memory ভুলে যাওয়া — N = 10¹²-এর spf array অসম্ভব; sieve variants ছোট/মাঝারি N-এ, বিশাল range-এ segmented (138)।

18. Harder problems that inherit this idea

• CSES — Counting Divisors / divisor-related (https://cses.fi/problemset/task/1713) — প্রচুর সংখ্যার দ্রুত factorization, SPF-এর আদর্শ ব্যবহার।
• Codeforces — multiplicative function precompute (φ, μ, divisor count) (https://codeforces.com/problemset) — linear sieve-এ একই pass-এ φ/μ বানানো।
• 138 (Segmented Sieve) — এই repo-রই পরের ধাপ; বিশাল range-এ যখন পুরো array অসম্ভব। ভিত্তি 015; সঙ্গী 128, 129 (multiplicative)।

19. Pattern learned

SPF / linear sieve for fast factorization — Eratosthenes-এ কাটার সময় smallest prime factor টুকে রাখো; তখন factorization O(log n) (spf ধরে ভাগ)। linear sieve প্রতিটা composite একবার কেটে O(N)। বড় শিক্ষা: একবার precompute করে "কে কাটল" মনে রাখলে, পরের হাজারো query-তে কাজ প্রায় শূন্য — sieve শুধু prime খোঁজার নয়, factorization-এর lookup table।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "SPF sieve: কাটার সময় ক্ষুদ্রতম prime টুকে রাখো (if spf[j]==j); factorize = spf ধরে ভাগ O(log n); linear sieve প্রতিটা composite একবার কেটে O(N); spf[n]==n মানে prime।" Signal: "প্রচুর সংখ্যার factorization/prime-চেক" বা "1..N-এ multiplicative function precompute" — দেখলেই sieve variants মনে পড়বে।

পরের ধাপ → 138 — Segmented Sieve (বিশাল range-এ window-ভিত্তিক sieve)। ভিত্তি → 015 (Sieve of Eratosthenes)।

ফিরে দেখা: এই 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" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।