Problem link ও উৎস
- **Original source:** CP-Algorithms — Linear Sieve
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Medium
- **Pattern:** SPF / linear sieve
- **Basic idea inherited from:** 015 (Sieve of Eratosthenes)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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-চিন্তা সর্বত্র কাজে লাগে।
### Input ও output {#6-example-input-and-output}
```text
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)-এ।
### চেনা উদাহরণে বোঝা {#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 জিজ্ঞেস করলে সঙ্গে সঙ্গে উত্তর — পুরো লাইব্রেরি আবার চষতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর সাথে মেলে।
### ভেতরের অঙ্ক {#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 বিনামূল্যে।"
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
precompute ছাড়া — **প্রতিটা সংখ্যা আলাদা করে trial division-এ factorize** (134-এর মতো):
```python
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**-তে:
```text
একটা 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-ভিত্তিক):**
```text
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)):**
```text
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-এর সাথে মেলে।
### ছবিতে বোঝা {#5-visual-explanation}
SPF sieve দিয়ে 60-এর factorization — আগে spf array, তারপর ভাগ:
```text
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)।
### ছোট input-এ ধাপে ধাপে {#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 থেকে সরাসরি।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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!`।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Divisors / divisor-related** (