015 — Sieve of Eratosthenes¶

014-এ তুমি টের পেয়েছ — এক-একটা সংখ্যাকে আলাদা করে prime check করলে N বড় হলে ধীর। আজ সেই সমস্যার বিখ্যাত সমাধান: প্রায় ২৩০০ বছরের পুরোনো গ্রিক গণিতবিদ Eratosthenes-এর চালুনি। মূল চিন্তা-বদল একটাই কিন্তু গভীর — prime খুঁজো না, composite-দের কেটে ফেলো; যারা বেঁচে থাকবে তারাই prime। এই "search → mark" দৃষ্টিভঙ্গি, আর "একবার কারখানা বানাও, তারপর হাজার query free" (precompute) ধারণা — পুরো competitive programming জুড়ে ফিরবে। grid-টা নিজে হাতে এঁকে কাটাকাটি করো, একবার করলেই গেঁথে যাবে।

Source¶

Original source: CP-Algorithms — Sieve of Eratosthenes (https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)
Platform: CP-Algorithms (related: LeetCode — Count Primes — https://leetcode.com/problems/count-primes/)
Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
Difficulty: Medium
Pattern: sieve
Basic idea inherited from: 014 (Print All Primes up to N)

1. Problem in simple words¶

একটা সংখ্যা N দেওয়া আছে। 2 থেকে N পর্যন্ত সব prime বের করতে হবে — ঠিক 014-এর মতোই কাজ, কিন্তু এবার অনেক দ্রুত, যাতে N বড় (10⁶, 10⁷) হলেও চলে।

কৌশল: একটা boolean তালিকা বানাও যেখানে শুরুতে সবাই "prime" ধরা; তারপর প্রতিটা prime-এর গুণিতকগুলো "composite" বলে দাগিয়ে দাও। শেষে যাদের দাগ পড়েনি, তারাই prime।

2. What is the math idea?¶

মূল idea — multiples কেটে ফেলা (marking composites)। যদি p একটা prime হয়, তবে 2p, 3p, 4p, ... — এর সব গুণিতকই composite (কারণ এদের p একটা factor)। তাই prime খুঁজে খুঁজে না বের করে, প্রতিটা prime-এর গুণিতক একসাথে বাদ দিই:

is_prime = [True] * (N+1)        # শুরুতে সবাই prime ধরা
is_prime[0] = is_prime[1] = False
প্রতিটা i, 2 থেকে √N পর্যন্ত:
    যদি is_prime[i] (i বেঁচে আছে = prime):
        i*i, i*i+i, i*i+2i, ... কেটে দাও (False করো)
যারা এখনো True, তারাই prime

দুটো সূক্ষ্ম গণিত: (১) marking শুরু i*i থেকে — কারণ i-এর ছোট গুণিতক (2i, 3i...) আরও ছোট prime-এর হাতে আগেই কাটা; (২) i শুধু √N পর্যন্ত — তার বড় prime-এর গুণিতক সব আগেই কাটা পড়েছে।

3. Which basic idea does this inherit from?¶

সরাসরি 014 (Print All Primes up to N) থেকে — একই লক্ষ্য (N পর্যন্ত সব prime), কিন্তু উল্টো পদ্ধতি।

014:  প্রতিটা num-কে জিজ্ঞেস করো "তুমি prime?" (search)  -> O(N√N)
015:  প্রতিটা prime-এর গুণিতক কেটে দাও (mark)            -> O(N log log N)

014-এ আমরা প্রতিটা সংখ্যায় আলাদা √n check চালাতাম — একই composite বারবার পরীক্ষা হতো (অপচয়)। 015 সেই অপচয় দূর করে: 30 যে composite, সেটা 2-এর গুণিতক কাটার সময়ই একবার দাগিয়ে দিই, আর কখনো ফিরে দেখি না। 014-এর "এই অপচয় কাটানো যায় কি?" প্রশ্নের সরাসরি উত্তরই এই Sieve। তাই 014 না বুঝলে কেন Sieve দরকার সেটাই অস্পষ্ট থাকবে।

4. Real-life analogy¶

ভাবো একটা বিশাল হলঘরে সব ছাত্র দাঁড়িয়ে, নম্বর 2, 3, 4, ... N। তুমি "prime" ছাত্রদের খুঁজে বের করতে চাও, কিন্তু এক-একজনকে আলাদা করে প্রশ্ন করা সময়সাপেক্ষ। তাই উল্টো খেলো:

প্রথম দাঁড়ানো ছাত্র 2 — সে prime। ঘোষণা করো: "2-এর নামতার সবাই (4, 6, 8...) বসে পড়ো" (composite, কাটা)।
পরের দাঁড়ানো ছাত্র 3 — সে-ও prime। "3-এর নামতার সবাই বসে পড়ো।"
পরের দাঁড়ানো 5 — prime। "5-এর নামতা বসো।"
... যতক্ষণ দাঁড়ানো ছাত্রের নম্বরের বর্গ N ছাড়ায়, খেলা শেষ।
শেষে যারা এখনো দাঁড়িয়ে — তারাই prime।

মানে তুমি prime খোঁজোনি; composite-দের বসিয়ে দিয়েছ, দাঁড়িয়ে থাকারাই উত্তর। এটাই চালুনির মূল চাল।

5. Visual explanation¶

2 থেকে 30-এর grid-এ কাটাকাটির খেলা ধাপে ধাপে (x = কাটা/composite):

শুরুতে সবাই prime ধরা:
 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ... 30

ধাপ 1 (i=2, বাঁচল): 2-এর গুণিতক 4 থেকে কাটো (4,6,8,...):
 2  3  x  5  x  7  x  9  x 11  x 13  x 15  x 17  x 19  x ...

ধাপ 2 (i=3, বাঁচল): 3-এর গুণিতক 9 থেকে কাটো (9,15,21,27; 6,12 আগেই কাটা):
 2  3  x  5  x  7  x  x  x 11  x 13  x  x  x 17  x 19  x ...

ধাপ 3 (i=4): is_prime[4]=False, skip।
ধাপ 4 (i=5): 5×5=25 কাটো; পরের i=6-এ 6×6=36 > 30 -> খেলা শেষ!

বেঁচে রইল: 2 3 5 7 11 13 17 19 23 29  -> এরাই prime

এক বাক্যে: প্রতিটা বেঁচে-থাকা i-এর গুণিতক i² থেকে কেটে যাও; শেষে অদাগি সংখ্যাগুলোই prime।

6. Example input and output¶

sieve(N)
-------------------------------------------------
sieve(30) -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
sieve(10) -> [2, 3, 5, 7]
sieve(2)  -> [2]
sieve(1)  -> []          <-- 2-এর নিচে prime নেই
sieve(0)  -> []
count_primes(30) -> 10   (গোনা চাইলে শুধু True-গুলো গুনি)

Edge case: N < 2 হলে খালি তালিকা। আর Sieve-এর বাড়তি উপহার — একবার is_prime তালিকা বানালে শুধু prime তালিকা নয়, "অমুক সংখ্যা prime কিনা" — যেকোনো query O(1)-তে উত্তর (precompute-এর শক্তি)।

7. Brute force thinking¶

"Brute force" এখানে আসলে 014-এর পদ্ধতি — প্রতিটা সংখ্যাকে আলাদা করে √n trial division দিয়ে check:

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def primes_brute(N):
    return [num for num in range(2, N + 1) if is_prime(num)]

এটা ঠিক উত্তর দেয়, ছোট N-এ একদম চলে। কিন্তু প্রতিটা সংখ্যায় আলাদা check মানে একই composite বারবার পরীক্ষা — সেই অপচয়টাই Sieve দূর করবে।

8. Why brute force may be slow¶

014-এর হিসাবটাই ফিরে আসে — মোট খরচ O(N√N):

N = 10^7 হলে:
  trial-division (014) : O(N√N) ≈ 10^7 × 3162 ≈ 3×10^10   -> মিনিটের হিসাব, TLE
  Sieve (015)          : O(N log log N) ≈ 10^7 × ~3 ≈ 3×10^7 -> সেকেন্ডের ভগ্নাংশ

কোথায় অপচয়? 30-কে check করতে গিয়ে আমরা 30 % 2, 30 % 3, 30 % 5... পরীক্ষা করি; আবার 60-এর জন্য আলাদা করে 60 % 2, 60 % 3... — অর্থাৎ 2 যে অনেক সংখ্যাকে কাটে, সেই জ্ঞান বারবার নতুন করে আবিষ্কার করছি। Sieve একবার 2-এর সব গুণিতক কেটে দিয়ে এই পুনরাবৃত্তি পুরো বাদ দেয়। এটাই O(N√N) থেকে O(N log log N)-এ নামার রহস্য।

9. Better thinking¶

মূল insight — boolean তালিকায় composite দাগাও, তারপর অদাগি = prime:

def sieve(N):
    if N < 2:
        return []
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= N:
        if is_prime[i]:                       # i বেঁচে আছে = prime
            for j in range(i * i, N + 1, i):  # i² থেকে i-এর গুণিতক কাটো
                is_prime[j] = False
        i += 1
    return [x for x in range(2, N + 1) if is_prime[x]]

দুটো জরুরি optimization code-এই দেখা যায়: (১) ভেতরের loop শুরু i * i থেকে (i*i+i ইত্যাদি — i-এর ছোট গুণিতক আগেই কাটা); (২) বাইরের loop শুধু i * i <= N পর্যন্ত (√N — তার বড় prime নিজে আর কাটার বাকি নেই, কিন্তু তালিকায় True হিসেবে থেকে যায়, ঠিকঠাক)।

10. Thinking tweak¶

মূল মোচড় এক বাক্যে: prime খুঁজো না — composite কেটে ফেলো; যারা বেঁচে থাকে তারাই prime (search → mark)।

এর সাথে দুটো সূক্ষ্ম tweak, যেগুলো না বুঝলে Sieve "জাদু" মনে হয়:

i² থেকে কাটা শুরু: i-এর গুণিতক 2i, 3i, ..., (i-1)i — এদের প্রত্যেকের একটা ছোট factor (2, 3, ..., i-1) আছে, তাই আগের prime-রা এদের আগেই কেটেছে। নতুন করে কাটার দরকার শুধু i² থেকে।
√N পর্যন্ত বাইরের loop: N-এর প্রতিটা composite-এর একটা prime factor ≤ √N থাকবেই (012-এর জোড়ার যুক্তি), তাই √N পর্যন্ত কাটলেই সব composite ধরা পড়ে।

আর বড় দার্শনিক tweak — precompute: একবার চালুনি চালিয়ে তালিকা বানালে, তারপর "x কি prime?" হাজারবার জিজ্ঞেস করলেও প্রতিবার O(1)। কারখানা একবার, পণ্য বহুবার।

11. Step-by-step dry run¶

N = 20 দিয়ে হাতে চালাই। i * i <= 20 মানে i যাবে 2, 3, 4 (5×5=25 > 20)। শুরুতে 0,1 বাদে সবাই True:

i	is_prime[i]?	i²	কী কাটা পড়ে (j = i², i²+i, ...)
2	True	4	4, 6, 8, 10, 12, 14, 16, 18, 20
3	True	9	9, 12(আগেই), 15, 18(আগেই) → নতুন: 9, 15
4	False (4 কাটা পড়েছে)	—	skip — কিছু কাটি না

i = 5-এ 25 > 20, বাইরের loop থামল। এখন True যারা: 2, 3, 5, 7, 11, 13, 17, 19 (4,6,8,9,10,12,14,15,16,18,20 কাটা পড়েছে)। চূড়ান্ত [2, 3, 5, 7, 11, 13, 17, 19] — ঠিক 20 পর্যন্ত সব prime। লক্ষ করো i=4-এ skip করলাম — 4 আগেই composite, তার গুণিতক কাটার দরকার নেই (কাটা হয়েও গেছে 2-এর দ্বারা)।

12. Python solution¶

def sieve(N):
    """2 থেকে N পর্যন্ত সব prime — Sieve of Eratosthenes, O(N log log N)।"""
    if N < 2:
        return []
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= N:
        if is_prime[i]:                        # i বেঁচে = prime
            for j in range(i * i, N + 1, i):   # i² থেকে গুণিতক কাটো
                is_prime[j] = False
        i += 1
    return [x for x in range(2, N + 1) if is_prime[x]]


def count_primes(N):
    """N পর্যন্ত prime সংখ্যা (একই sieve, শুধু গোনা)।"""
    return len(sieve(N))


def is_prime_trial(n):
    """ছোট, স্বাধীন trial-division — sieve যাচাইয়ের জন্য।"""
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sieve(30) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
assert sieve(10) == [2, 3, 5, 7]
assert sieve(2) == [2]              # সবচেয়ে ছোট prime
assert sieve(1) == []              # 2-এর নিচে কিছু নেই
assert sieve(0) == []
assert sieve(13) == [2, 3, 5, 7, 11, 13]   # N নিজে prime, ধরা পড়ে

# sieve আর trial division — সব N-এ মেলে কিনা (সোনার নিয়ম)
for N in range(0, 200):
    assert sieve(N) == [x for x in range(2, N + 1) if is_prime_trial(x)]

assert count_primes(30) == 10
assert count_primes(100) == 25     # 100 পর্যন্ত ঠিক 25টা prime

print(sieve(30))         # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(sieve(10))         # [2, 3, 5, 7]
print(count_primes(100)) # 25
print("সব test pass!")

13. Line-by-line explanation¶

    if N < 2:
        return []

2-এর নিচে prime নেই — খালি তালিকা (edge case)।

    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False

N + 1 ঘরের তালিকা (index 0..N), শুরুতে সবাই True ("ধরে নিলাম prime")। তারপর 0 আর 1 হাতে-হাতে False — কারণ এরা prime নয়। (N + 1 জরুরি, যাতে index N-ও থাকে।)

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

বাইরের loop √N পর্যন্ত (i * i <= N, integer)। if is_prime[i] — i এখনো অদাগি মানে i prime; তবেই তার গুণিতক কাটার মানে আছে (composite i-এর গুণিতক আগেই কাটা পড়েছে)।

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

চালুনির হৃদয়। i² থেকে শুরু করে i ধাপে (i², i²+i, i²+2i...) — i-এর গুণিতকগুলো False করি। i² থেকে শুরু, কারণ ছোট গুণিতক আগেই কাটা।

    return [x for x in range(2, N + 1) if is_prime[x]]

শেষে যারা এখনো True, তাদের তালিকা — এরাই prime।

for N in range(0, 200) loop sieve-কে স্বাধীন trial division-এর সাথে 200টা N-এ মিলিয়ে যাচাই করে। count_primes(100) == 25 একটা চেনা সত্য দিয়ে অতিরিক্ত নিশ্চয়তা। সব মিললে সব test pass!।

14. Output walkthrough¶

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

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

প্রথম দুই লাইন sieve(30) ও sieve(10) — 30 ও 10 পর্যন্ত prime তালিকা। তৃতীয় লাইন count_primes(100) → 25 (100 পর্যন্ত ঠিক 25টা prime)। তার আগে সব assert — নির্দিষ্ট কেস, 0..199 জুড়ে sieve-বনাম-trial মিল, আর গোনা — চুপচাপ pass করেছে। শেষ লাইন সব test pass! মানে চালুনি সব ক্ষেত্রে সঠিক।

15. Time complexity¶

O(N log log N) — মোট কাজ ≈ N/2 + N/3 + N/5 + N/7 + ... (শুধু prime-দের জন্য গুণিতক কাটা), যার যোগফল গাণিতিকভাবে N log log N-এর কাছাকাছি — প্রায় linear, আশ্চর্য দ্রুত। N = 10⁷-এও সেকেন্ডের ভগ্নাংশ। (trial-division O(N√N)-এর তুলনায় বিশাল উন্নতি।)

16. Space complexity¶

O(N) — is_prime boolean তালিকায় N+1 ঘর লাগে। এটাই Sieve-এর একমাত্র বড় খরচ; তাই খুব বিশাল N (যেমন 10⁹) হলে স্মৃতি একটা সীমাবদ্ধতা (তখন segmented sieve বা bit-packing লাগে)। সময় বাঁচাতে এই জায়গাটুকু খরচ — classic time-space tradeoff।

17. Common mistakes¶

ভেতরের loop 2*i থেকে শুরু করা — কাজ করে (ভুল উত্তর দেয় না), কিন্তু অপচয়; i*i থেকে শুরু করলে ছোট গুণিতক পুনরায় কাটার পরিশ্রম বাঁচে।
বাইরের loop N পর্যন্ত চালানো — i * i <= N-এ থামাই; N পর্যন্ত চালালে ভুল হয় না, কিন্তু অপ্রয়োজনীয় (√N-এর পর কিছু কাটার নেই)।
is_prime[0] / is_prime[1] False করতে ভুলে যাওয়া — না করলে 0 আর 1 ভুল করে prime হিসেবে তালিকায় চলে আসবে।
তালিকার আকার N (N+1 নয়) — index N ধরতে [True] * (N + 1) লাগে; শুধু N হলে শেষ সংখ্যাটায় IndexError বা বাদ।
খুব বড় N-এ স্মৃতি ভুলে যাওয়া — O(N) space; N = 10⁹ হলে সাধারণ boolean তালিকা মেমরি ছাড়িয়ে যাবে — তখন অন্য কৌশল ভাবতে হয়।

18. Harder problems that inherit this idea¶

017 — Smallest Prime Factor (SPF) sieve (এই repo) — একই কাটাকাটি, কিন্তু True/False-এর বদলে প্রতিটা ঘরে "প্রথম কে কাটল" লিখে রাখা; পরে O(log n)-এ factorization। সরাসরি পরের ধাপ।
LeetCode — Count Primes (https://leetcode.com/problems/count-primes/) — N পর্যন্ত prime গোনা; বড় N বলে Sieve-ই মানক সমাধান।
CP-Algorithms — Sieve variants (https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html) — segmented sieve, linear sieve — এই idea-র উন্নত রূপ, খুব বড় range বা প্রতি সংখ্যার smallest factor চাইলে।

19. Pattern learned¶

Sieve = mark composites, survivors are prime। বড় শিক্ষা: একই কাজ বারবার (per-number check) করার বদলে একসাথে precompute করলে O(N√N) থেকে O(N log log N)-এ নামা যায়; আর i² থেকে কাটা + √N পর্যন্ত loop — এই দুই optimization Sieve-কে প্রায়-linear করে। এই "search → mark" আর "একবার কারখানা, বহু query free" দৃষ্টিভঙ্গি পুরো CP জুড়ে কাজে লাগবে।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Sieve = [True]*(N+1), 0/1 False; i*i <= N পর্যন্ত যদি is_prime[i], তবে range(i*i, N+1, i) কাটো; অদাগিরাই prime। i² থেকে শুরু, √N পর্যন্ত — এই দুই trick-এ O(N log log N)। prime খুঁজো না, composite কাটো। O(N) space।"

আগের ধাপ → 014 — Print All Primes up to N (যে অপচয় কাটাতে এই Sieve)। পরের ধাপ → 017 — Smallest Prime Factor (একই চালুনিতে factor লিখে রাখা)। সম্পর্কিত শিকড় → 013 — Check Prime।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)¶

JS-এ boolean array বানাতে new Array(N + 1).fill(true) — তারপর Python-এর মতোই composite কেটে যাই।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function sieve(N) {
  if (N < 2) return [];
  const isPrime = new Array(N + 1).fill(true);  // শুরুতে সবাই prime
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= N; i++) {            // √N পর্যন্ত
    if (isPrime[i]) {
      for (let j = i * i; j <= N; j += i) {     // i² থেকে গুণিতক কাটো
        isPrime[j] = false;
      }
    }
  }
  const out = [];
  for (let x = 2; x <= N; x++) if (isPrime[x]) out.push(x);
  return out;
}

const countPrimes = (N) => sieve(N).length;

// trial division — sieve যাচাইয়ের জন্য
function isPrimeTrial(n) {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;
  return true;
}

// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(sieve(30), [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]), "30");
assert(eq(sieve(10), [2, 3, 5, 7]), "10");
assert(eq(sieve(2), [2]), "2 — সবচেয়ে ছোট prime");
assert(eq(sieve(1), []), "1 → খালি");
assert(eq(sieve(0), []), "0 → খালি");
assert(eq(sieve(13), [2, 3, 5, 7, 11, 13]), "N নিজে prime");
// sieve বনাম trial division — 0..120 জুড়ে মিল
for (let N = 0; N <= 120; N++) {
  const ref = [];
  for (let x = 2; x <= N; x++) if (isPrimeTrial(x)) ref.push(x);
  assert(eq(sieve(N), ref), "cross-check N=" + N);
}
assert(countPrimes(100) === 25, "100 → 25");
console.log("সব JS test pass!");

JS টীকা: Array(N+1).fill(true) না লিখে শুধু new Array(N+1) করলে ঘরগুলো empty (undefined) থাকে — if (isPrime[i]) তখন falsy ধরে ভুল করবে; তাই .fill(true) জরুরি। খুব বড় N-এ Uint8Array মেমরি অনেক কম খায়।

22. TypeScript solution (with test cases)¶

function sieve(N: number): number[] {
  if (N < 2) return [];
  const isPrime: boolean[] = new Array(N + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= N; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= N; j += i) isPrime[j] = false;
    }
  }
  const out: number[] = [];
  for (let x = 2; x <= N; x++) if (isPrime[x]) out.push(x);
  return out;
}

function expectArr(actual: number[], expected: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(expected)) {
    throw new Error(`FAIL ${msg}: [${actual}]`);
  }
}

expectArr(sieve(30), [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], "30");
expectArr(sieve(10), [2, 3, 5, 7], "10");
expectArr(sieve(1), [], "1");
expectArr(sieve(13), [2, 3, 5, 7, 11, 13], "13");
console.log("সব TS test pass!");

TS টীকা: isPrime: boolean[] আর return type number[] declare করলে ভুলে string push করা বা boolean index করার মতো ভুল compile-time-এ ধরা পড়ে — sieve-এর index/value gड़बड़ আগেই আটকায়।

23. কোথায় কাজে লাগে (real-world use)¶

Precompute + many queries: একবার sieve চালিয়ে একটা range-এর সব prime/factor জেনে রাখা, তারপর হাজার query O(1)-তে — competitive programming-এ নিত্য।
Number-theory pipeline: prime factorization, divisor count, Euler phi — সব smallest-prime-factor sieve-এর উপর দাঁড়ায়।
Cryptography setup: নির্দিষ্ট bound-এর নিচে prime তালিকা তৈরি (key generation, testing-এর প্রাথমিক ধাপ)।
General "mark instead of search" tasks: graph-এ visited marking, dynamic programming table fill — "খুঁজো না, দাগাও; বাকিরা উত্তর" এই দৃষ্টিভঙ্গির ছোট রূপ। মূল pattern — "search → mark, একবার কারখানা বহু query free" — caching, memoization, precomputation জুড়ে বড় ছবিতে ফেরে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য রাখা; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" হিসেবে লেখা।