Skip to content

138 — Segmented Sieve

Level 10-এর শেষ problem — অভিনন্দন, এতদূর এলে! 137-এ sieve variants দেখলে; কিন্তু range যখন বিশাল (R = 10¹²) আর পুরো array রাখা অসম্ভব, তখন? এই note-এ segmented sieve — Eratosthenes-কে একটা ছোট window-তে নামিয়ে আনা। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — segmented sieve interview-তে আসেই না, কিন্তু CP-তে "বড় range-এ prime" problem-এর মূল কৌশল। 137 (sieve variants) ভালো বুঝে থাকলে এটা তার স্বাভাবিক সম্প্রসারণ।

Source

  • Original source: CP-Algorithms — Sieve of Eratosthenes (segmented section)
  • Platform: CP-Algorithms — https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
  • Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
  • Difficulty: Hard
  • Pattern: windowed sieve
  • Basic idea inherited from: 137 (Sieve Variants)

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-চিন্তা সর্বত্র কাজে লাগে।

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 ছাঁকো।"

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)-এ নামানো।

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 দিয়ে ছাঁকা।

5. Visual explanation

[L, R] = [10, 30]-এর prime — base prime ≤ √30 ≈ 5.4, মানে {2, 3, 5}:

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-র ভেতরে সঠিক জায়গা থেকে কাটছি।

6. Example input and output

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-ও অল্প।

7. Brute force thinking

সরলতম — window-র প্রতিটা সংখ্যা আলাদা করে primality test (134-এর trial division):

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):

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 লাগে না। ধাপ:

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 থেকে শুরু।

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

12. Python solution

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

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

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 মিস হতে পারে।

18. Harder problems that inherit this idea

  • CSES — Counting Primes / বড় range prime (https://cses.fi/problemset/) — যেখানে R বিশাল কিন্তু পুরো sieve অসম্ভব।
  • Codeforces / SPOJ — PRIME1-ধাঁচের "primes in [L, R]" problems (https://codeforces.com/problemset) — segmented sieve-এর classic প্রয়োগ।
  • 137 (Sieve Variants) আর 015 (Eratosthenes) — এই repo-রই ভিত্তি; segmented sieve তাদেরই window-রূপ। এই দিয়ে Level 10 সম্পূর্ণ।

19. Pattern learned

Windowed sieve for huge ranges — √R পর্যন্ত base prime বানিয়ে, [L, R] window-তে তাদের গুণিতক কাটো (offset max(p², ⌈L/p⌉·p), index −L); memory O(R) → O(√R + window)। বড় শিক্ষা: বিশাল range পুরোটা একসাথে ধরার দরকার নেই — composite চিনতে শুধু √R পর্যন্ত prime লাগে, তাই কাজটাকে একটা ছোট window-তে নামিয়ে আনো।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "segmented sieve: √R পর্যন্ত base prime, [L,R] window-এ গুণিতক কাটো start = max(p², ⌈L/p⌉·p), index multiple−L; L=max(L,2); memory O(√R + window), পুরো R নয়।" Signal: "[L, R]-এ prime, R বিশাল, window ছোট" — দেখলেই segmented sieve মনে পড়বে।

এটাই Level 10-এর শেষ problem! পরের ধাপ → Level 11: Hard Mixed CP Patterns (interview-পথিক হলে মূল DS topic গুলোই যথেষ্ট — এখানে যা শিখলে, bonus মশলা)। ভিত্তি → 137 — Sieve Variants, 015 (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।