Problem link ও উৎস
- **Original source:** CP-Algorithms — Sieve of Eratosthenes (segmented section)
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Hard
- **Pattern:** windowed sieve
- **Basic idea inherited from:** 137 (Sieve Variants)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা range `[L, R]` দেওয়া আছে যেখানে **R খুব বড়** (যেমন 10¹²), কিন্তু **window-টা ছোট** (R − L ≤ 10⁶)। বের করতে হবে এই range-এর মধ্যে সব **prime**।
সমস্যা: সাধারণ sieve-এ 0 থেকে R পর্যন্ত একটা array লাগত — কিন্তু R = 10¹² মানে 10¹² আকারের array, যা memory-তে অসম্ভব (টেরাবাইট লাগবে)।
**Segmented sieve-এর সমাধান:** পুরো R নয় — শুধু `√R` পর্যন্ত prime গুলো সাধারণ sieve-এ বানাও (এটা ছোট, ~10⁶), তারপর শুধু `[L, R]` window-র একটা ছোট array-তে (আকার R − L + 1) সেই prime-দের গুণিতক কেটে দাও। যা টিকে থাকে, তারাই window-র prime। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু "বড় সমস্যাকে ছোট window-তে নামানো" — এই memory-চিন্তা সর্বত্র কাজে লাগে।
### Input ও output {#6-example-input-and-output}
```text
input (L, R) -> primes in [L, R]
----------------------------------------------------------------
10, 30 -> [11, 13, 17, 19, 23, 29]
1, 10 -> [2, 3, 5, 7]
90, 100 -> [97]
2, 2 -> [2] (single prime)
1, 1 -> [] (1 prime নয়)
1000000, 1000100 -> [1000003, 1000033, 1000037, 1000039, ...]
999999999989, 999999999999 -> [999999999989, ...] (R ~ 10¹², window ছোট)
```
খেয়াল করো: **L = 1 হলে 1-কে বাদ দিতে হবে** (1 prime নয়) — গুরুত্বপূর্ণ edge case। আর R ~ 10¹²-এর কাছাকাছি window-ও কাজ করে, কারণ আমরা শুধু √R ≈ 10⁶ পর্যন্ত prime আর (R−L+1) আকারের window রাখি — পুরো 10¹² array নয়। window ছোট হলে (যেমন 11) base prime-ও অল্প।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমাকে একটা বিশাল বইয়ের (R = 10¹² পৃষ্ঠা) মধ্যে শুধু 1,000,000তম থেকে 1,001,000তম পৃষ্ঠার "বিশেষ পৃষ্ঠা" (prime) খুঁজতে হবে। পুরো বই টেবিলে রাখা অসম্ভব — খুব ভারী।
চালাক উপায়: তুমি জানো বিশেষ পৃষ্ঠা চিনতে শুধু কয়েকটা ছোট "চিহ্নিতকারী নিয়ম" (√R পর্যন্ত prime) লাগে। তাই —
- আগে শুধু সেই ছোট নিয়মগুলো একটা কার্ডে লিখে নাও (base sieve, ছোট)।
- তারপর শুধু তোমার দরকারি 1,000-পৃষ্ঠার অংশটুকু (window) টেবিলে রাখো, আর কার্ডের নিয়ম প্রয়োগ করে অ-বিশেষ পৃষ্ঠাগুলো কেটে দাও।
পুরো বই কখনো একসাথে রাখলে না — শুধু একটা ছোট window আর একটা ছোট নিয়ম-কার্ড। এটাই segmented sieve: বড় range-কে ছোট window-তে নামিয়ে, ছোট prime দিয়ে ছাঁকা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **137 (Sieve Variants)**, আর তার মূল 015 (Eratosthenes)। segmented sieve হলো Eratosthenes-এরই দুই-ধাপ রূপ — base sieve অংশটা হুবহু 137/015-এর সাধারণ sieve, আর segment অংশটা সেই "গুণিতক কেটে দাও" কৌশলকে একটা সরানো window-তে (offset L সহ) প্রয়োগ।
পেছনে √n-এর যুক্তি (134, 137)। এটা sieve জোড়ার (137 → 138) শেষ, আর পুরো Level 10-এর সমাপ্তি। README-র recommended order: 137 → 138। মূল নতুনত্ব — memory O(R) থেকে O(R−L)-এ নামানো।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **prime কাটতে হলে √R পর্যন্ত prime-ই যথেষ্ট।** কারণ যেকোনো composite m ≤ R-এর অন্তত একটা prime factor ≤ √m ≤ √R থাকবেই (137/134-এর সেই যুক্তি)। তাই `[L, R]` window-র composite-দের কাটতে শুধু √R পর্যন্ত prime দরকার — পুরো R পর্যন্ত নয়।
দুই ধাপ:
- **ধাপ ১ (base sieve):** 2 থেকে √R পর্যন্ত সব prime সাধারণ Eratosthenes-এ বানাও (ছোট array)।
- **ধাপ ২ (segment):** `[L, R]` window-র জন্য আকার (R−L+1)-এর একটা boolean array নাও (সব True ধরে); প্রতিটা base prime p-এর জন্য window-র ভেতরে p-এর গুণিতক False করো।
window-এ p-এর **প্রথম গুণিতক** কোথায়? `max(p·p, ⌈L/p⌉·p)` — মানে p² থেকে (ছোট গুণিতক base sieve-এ কাটা) বা L-এর ≥ প্রথম p-গুণিতক, যেটা বড়। এই ceiling-multiple হিসাবটাই segmented sieve-এর হৃদয়। এই level CP-leaning হলেও মূল সুর সরল — "ছোট prime দিয়ে বড় window ছাঁকো।"
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরলতম — **window-র প্রতিটা সংখ্যা আলাদা করে primality test (134-এর trial division)**:
```python
def primes_in_range_brute(L, R):
def is_prime(n):
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
return [n for n in range(L, R + 1) if is_prime(n)]
```
ছোট range-এ নিখুঁত — প্রতিটা সংখ্যা trial division-এ চেক। আমরা segmented sieve-এর উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। শুরুর জন্য পরিষ্কার ও নির্ভরযোগ্য।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
window-র প্রতিটা সংখ্যায় O(√n) primality test — মোট O((R−L) · √R):
```text
window 10⁶, R ~ 10¹²: (R−L) × √R = 10⁶ × 10⁶ = 10¹² ভাগ — অসম্ভব
segmented sieve: base sieve O(√R log log √R) + segment O((R−L) log log R)
≈ 10⁶ + 10⁶ — তাৎক্ষণিক
```
প্রতিটা সংখ্যা আলাদা trial division করলে, R বড় হলে (√R বড়) মোট কাজ বিশাল। segmented sieve প্রতিটা base prime দিয়ে window-এ সরাসরি গুণিতক কাটে (প্রতি সংখ্যা amortized প্রায় ধ্রুবক বার ছোঁয়া) — তাই অনেক দ্রুত। মূল সাশ্রয়: ভাগের বদলে গুণিতক-কাটা।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **√R পর্যন্ত prime দিয়ে window ছাঁকো, পুরো R পর্যন্ত array লাগে না।** ধাপ:
```text
1. base sieve: 2..√R পর্যন্ত সব prime বের করো (সাধারণ Eratosthenes, ছোট)
2. is_prime[0..R−L] = True (window, আকার R−L+1)
3. প্রতিটা base prime p-এর জন্য:
start = max(p·p, ⌈L/p⌉·p) [window-এ p-এর প্রথম গুণিতক]
start থেকে R, ধাপ p: is_prime[multiple − L] = False
4. L == 1 হলে is_prime[0] (সংখ্যা 1) = False
5. যেসব index True, তাদের (index + L)-ই prime
```
offset হিসাবের যত্ন: `⌈L/p⌉ = (L + p − 1) // p`, তাই `start = max(p*p, ((L + p − 1) // p) * p)`। `p·p` কেন: p-এর চেয়ে ছোট গুণনীয়কওয়ালা গুণিতক আগের prime-এ কাটা, তাই p² থেকে শুরু (নিজেকে না কাটতে)। index-এ `− L` দিয়ে window-র সাপেক্ষে অবস্থান।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **পুরো range sieve করার দরকার নেই — composite চিনতে শুধু √R পর্যন্ত prime লাগে, তাই বড় range-কে একটা ছোট window হিসেবে দেখে শুধু সেই prime-দের গুণিতক কাটলেই হয়।**
brute force প্রতিটা সংখ্যা আলাদা চেক করছিল (O((R−L)√R)); tweak হলো — base prime একবার বানিয়ে, window-এ তাদের গুণিতক সরাসরি কাটো (offset `max(p², ⌈L/p⌉·p)` দিয়ে)। সময় কমল, আর memory O(R) → O(√R + (R−L))-এ নামল। দ্বিতীয় tweak: index-এ `− L` shift — window-কে 0-ভিত্তিক array হিসেবে ভাবা, যেন L = 0 থেকে শুরু।
### ছবিতে বোঝা {#5-visual-explanation}
`[L, R] = [10, 30]`-এর prime — base prime ≤ √30 ≈ 5.4, মানে {2, 3, 5}:
```text
window: [10, 11, 12, ..., 30], আকার 21, সব শুরুতে True (prime ধরে)
base prime {2, 3, 5} দিয়ে কাটি:
p = 2: window-এ প্রথম গুণিতক = max(2·2, ⌈10/2⌉·2) = max(4, 10) = 10
কাটি: 10,12,14,16,18,20,22,24,26,28,30 -> False
p = 3: প্রথম গুণিতক = max(9, ⌈10/3⌉·3) = max(9, 12) = 12
কাটি: 12,15,18,21,24,27,30 -> False
p = 5: প্রথম গুণিতক = max(25, ⌈10/5⌉·5) = max(25, 10) = 25
কাটি: 25, 30 -> False
টিকে রইল (True): 11, 13, 17, 19, 23, 29 <- [10,30]-এর prime ✓
```
লক্ষ করো — offset হিসাব `max(p·p, ⌈L/p⌉·p)`: p = 2-এ window L = 10 থেকে শুরু (p² = 4 < L), কিন্তু p = 5-এ p² = 25 > L, তাই 25 থেকে। এই ceiling-multiple-ই নিশ্চিত করে আমরা window-র ভেতরে সঠিক জায়গা থেকে কাটছি।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`segmented_sieve(10, 30)` — base prime ≤ √30 = {2, 3, 5}:
| ধাপ | কী করছি | মান |
| --- | --- | --- |
| 1 | base sieve 2..⌊√30⌋=5 → primes | [2, 3, 5] |
| 2 | is_prime[0..20] = True (window 10..30) | সব True |
| 3a | p = 2: start = max(4, ⌈10/2⌉·2) = max(4,10) = 10 | কাটি 10,12,...,30 |
| 3b | p = 3: start = max(9, ⌈10/3⌉·3) = max(9,12) = 12 | কাটি 12,15,...,30 |
| 3c | p = 5: start = max(25, ⌈10/5⌉·5) = max(25,10) = 25 | কাটি 25, 30 |
| 4 | L ≠ 1, তাই index 0 আলাদা সামলানো লাগে না | — |
| 5 | True index গুলো + L | prime সংগ্রহ |
True থাকা সংখ্যা: 11, 13, 17, 19, 23, 29 → এগুলোই **[10, 30]-এর prime** ✓ (section 5-এর সাথে হুবহু)। লক্ষ করো — p = 2-এ start = 10 (L থেকেই, কারণ p² = 4 < L), p = 5-এ start = 25 (p² = 25 > L)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def simple_sieve(limit):
"""2..limit পর্যন্ত সব prime (সাধারণ Eratosthenes)।"""
if limit < 2:
return []
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i * i, limit + 1, i):
is_prime[j] = False
return [i for i in range(2, limit + 1) if is_prime[i]]
def segmented_sieve(L, R):
"""[L, R]-এর সব prime — memory O(√R + (R−L))।"""
if R < 2 or L > R:
return []
L = max(L, 2) # 1 আর তার নিচে prime নয়
base_primes = simple_sieve(int(R**0.5) + 1) # √R পর্যন্ত prime
size = R - L + 1
is_prime = [True] * size
for p in base_primes:
# window-এ p-এর প্রথম গুণিতক
start = max(p * p, ((L + p - 1) // p) * p)
for multiple in range(start, R + 1, p):
is_prime[multiple - L] = False # − L দিয়ে window index
return [L + i for i in range(size) if is_prime[i]]
# --- ছোট test গুলো (সব pass করা উচিত) ---
def primes_in_range_brute(L, R):
def isp(n):
if n < 2: return False
d = 2
while d * d <= n:
if n % d == 0: return False
d += 1
return True
return [n for n in range(L, R + 1) if isp(n)]
# segmented বনাম brute — নানা range মেলাও
ranges = [(10, 30), (1, 10), (1, 1), (2, 2), (90, 100), (0, 50),
(100, 200), (1, 100), (50, 50), (97, 97), (98, 98)]
for L, R in ranges:
assert segmented_sieve(L, R) == primes_in_range_brute(L, R), f"[{L},{R}] অমিল"
# 1..N সম্পূর্ণ মিলবে simple_sieve-এর সাথে
assert segmented_sieve(1, 1000) == simple_sieve(1000)
# নির্দিষ্ট
assert segmented_sieve(10, 30) == [11, 13, 17, 19, 23, 29]
assert segmented_sieve(1, 1) == [] # 1 prime নয়
assert segmented_sieve(2, 2) == [2]
assert segmented_sieve(90, 100) == [97]
# বড় R, ছোট window — memory ছোট, তবু সঠিক
big = segmented_sieve(1000000, 1000100)
assert big == primes_in_range_brute(1000000, 1000100)
assert 1000003 in big and 1000033 in big
# খুব বড় R ~ 10¹², ছোট window — পুরো array ছাড়াই চলে
huge = segmented_sieve(10**12, 10**12 + 50)
assert huge == primes_in_range_brute(10**12, 10**12 + 50)
# prime গোনা: [1, 100]-এ 25টা
assert len(segmented_sieve(1, 100)) == 25
print(segmented_sieve(10, 30)) # [11, 13, 17, 19, 23, 29]
print(segmented_sieve(90, 100)) # [97]
print(segmented_sieve(10**12, 10**12 + 50)) # ~10¹²-এর কাছাকাছি prime
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def simple_sieve(limit):
...
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i * i, limit + 1, i):
is_prime[j] = False
```
সাধারণ Eratosthenes (137/015-এর মতো) — √R পর্যন্ত base prime বানায়। এগুলোই window ছাঁকার "নিয়ম-কার্ড"।
```
def segmented_sieve(L, R):
...
L = max(L, 2)
base_primes = simple_sieve(int(R**0.5) + 1)
size = R - L + 1
is_prime = [True] * size
```
L-কে অন্তত 2 করি (1 ও নিচে prime নয়)। √R পর্যন্ত base prime, আর window-র জন্য (R−L+1) আকারের array — পুরো R নয়, এটাই memory সাশ্রয়।
```
for p in base_primes:
start = max(p * p, ((L + p - 1) // p) * p)
for multiple in range(start, R + 1, p):
is_prime[multiple - L] = False
```
প্রতিটা base prime p-এর জন্য — window-এ প্রথম গুণিতক `max(p², ⌈L/p⌉·p)` থেকে শুরু করে p ধাপে সব গুণিতক False। `multiple − L` দিয়ে window-র 0-ভিত্তিক index। `p·p` থেকে শুরু কারণ ছোট গুণিতক আগের prime-এ কাটা (আর p নিজে prime, কাটা যাবে না)।
```
return [L + i for i in range(size) if is_prime[i]]
```
True থাকা index গুলোর প্রকৃত মান (`L + i`)-ই window-র prime।
বাকি test অংশে segmented বনাম brute (নানা range সহ edge), simple_sieve-এর সাথে [1, N] মিল, নির্দিষ্ট range, আর বড় R (10⁶ ও 10¹²-এর কাছাকাছি) ছোট window সব যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
[11, 13, 17, 19, 23, 29]
[97]
[1000000000039, 1000000000061, ...]
সব test pass!
```
`segmented_sieve(10, 30)` → [11, 13, 17, 19, 23, 29] (section 5/11-এর সাথে মিল)। `segmented_sieve(90, 100)` → [97] (90-100-এ একমাত্র prime)। `segmented_sieve(10**12, 10**12 + 50)` → ~10¹²-এর কাছাকাছি কয়েকটা prime — আর এটা **পুরো 10¹² array ছাড়াই** হলো (শুধু √R ≈ 10⁶ base + 51-আকার window)। তার আগে সব range brute-এর সাথে মিল — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√R · log log √R + (R − L + 1) · log log R)** — প্রথম অংশ base sieve (√R পর্যন্ত), দ্বিতীয় অংশ window ছাঁকা (প্রতিটা base prime দিয়ে গুণিতক কাটা, harmonic sum-এ log log)। কার্যত: base ~√R, window ~(R−L)। brute force-এর O((R−L)·√R)-এর তুলনায় বিশাল লাফ (R বড় হলে)। তাই R ~ 10¹², window 10⁶-এও তাৎক্ষণিক।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(√R + (R − L + 1))** — base prime array (~√R পর্যন্ত sieve) আর window array (R−L+1)। **পুরো R নয়** — এটাই segmented sieve-এর মূল অর্জন: memory O(R) → O(√R + window)। তাই R = 10¹²-এও (√R = 10⁶, window 10⁶) memory সামান্য, যেখানে সাধারণ sieve-এর 10¹² array অসম্ভব।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **window-এ প্রথম গুণিতকের offset ভুল** — সবচেয়ে কমন। `start = max(p*p, ((L + p − 1) // p) * p)` — ceiling-multiple হিসাবটা একবার খাতায় করে নাও; ভুল করলে কিছু composite না কাটা থাকে বা index out of range।
2. **`multiple − L` index shift ভুলে যাওয়া** — window 0-ভিত্তিক; প্রকৃত সংখ্যা থেকে L বিয়োগ করে index। না করলে IndexError বা ভুল কাটা।
3. **p² থেকে শুরু না করা** — p-এর ছোট গুণিতক আগের prime-এ কাটা; আর p নিজে prime, কাটা যাবে না — তাই `max(p², ...)`। শুধু `⌈L/p⌉·p` দিলে p নিজে কাটা পড়তে পারে।
4. **L = 1 (বা 0) সামলানো ভুল** — 1 prime নয়; `L = max(L, 2)` দিয়ে আগে সামলাও, নাহলে 1-কে prime বলবে।
5. **base sieve-এ √R-এর ভুল সীমা** — `int(R**0.5)` round-down করে; নিরাপত্তার জন্য `+ 1` (বড় R-এ float round-off এড়াতে), নাহলে সবচেয়ে বড় base prime মিস হতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Primes / বড় range prime** (