Problem link ও উৎস
- Original source: CP-Algorithms — Sieve of Eratosthenes (
)
- Platform: CP-Algorithms (related: LeetCode — 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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যা `N` দেওয়া আছে। 2 থেকে `N` পর্যন্ত **সব** prime বের করতে হবে — ঠিক 014-এর মতোই কাজ, কিন্তু এবার অনেক **দ্রুত**, যাতে N বড় (10⁶, 10⁷) হলেও চলে।
কৌশল: একটা boolean তালিকা বানাও যেখানে শুরুতে সবাই "prime" ধরা; তারপর প্রতিটা prime-এর গুণিতকগুলো "composite" বলে দাগিয়ে দাও। শেষে যাদের দাগ পড়েনি, তারাই prime।
### Input ও output {#6-example-input-and-output}
```text
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-এর শক্তি)।
### চেনা উদাহরণে বোঝা {#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-দের বসিয়ে দিয়েছ, দাঁড়িয়ে থাকারাই উত্তর। এটাই চালুনির মূল চাল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 দরকার সেটাই অস্পষ্ট থাকবে।
### ভেতরের অঙ্ক {#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-এর গুণিতক সব আগেই কাটা পড়েছে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
"Brute force" এখানে আসলে 014-এর পদ্ধতি — প্রতিটা সংখ্যাকে আলাদা করে √n trial division দিয়ে check:
```python
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)**:
```text
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:**
```python
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)। কারখানা একবার, পণ্য বহুবার।
### ছবিতে বোঝা {#5-visual-explanation}
2 থেকে 30-এর grid-এ কাটাকাটির খেলা ধাপে ধাপে (`x` = কাটা/composite):
```text
শুরুতে সবাই 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।**
### ছোট input-এ ধাপে ধাপে {#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-এর দ্বারা)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[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!` মানে চালুনি সব ক্ষেত্রে সঠিক।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ boolean array বানাতে `new Array(N + 1).fill(true)` — তারপর Python-এর মতোই composite কেটে যাই।
```javascript
// 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` মেমরি অনেক কম খায়।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
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ड़बड़ আগেই আটকায়।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **ভেতরের loop `2*i` থেকে শুরু করা** — কাজ করে (ভুল উত্তর দেয় না), কিন্তু অপচয়; `i*i` থেকে শুরু করলে ছোট গুণিতক পুনরায় কাটার পরিশ্রম বাঁচে।
2. **বাইরের loop N পর্যন্ত চালানো** — `i * i <= N`-এ থামাই; N পর্যন্ত চালালে ভুল হয় না, কিন্তু অপ্রয়োজনীয় (√N-এর পর কিছু কাটার নেই)।
3. **`is_prime[0]` / `is_prime[1]` False করতে ভুলে যাওয়া** — না করলে 0 আর 1 ভুল করে prime হিসেবে তালিকায় চলে আসবে।
4. **তালিকার আকার N (N+1 নয়)** — index N ধরতে `[True] * (N + 1)` লাগে; শুধু N হলে শেষ সংখ্যাটায় IndexError বা বাদ।
5. **খুব বড় N-এ স্মৃতি ভুলে যাওয়া** — O(N) space; N = 10⁹ হলে সাধারণ boolean তালিকা মেমরি ছাড়িয়ে যাবে — তখন অন্য কৌশল ভাবতে হয়।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **017 — Smallest Prime Factor (SPF) sieve** (এই repo) — একই কাটাকাটি, কিন্তু True/False-এর বদলে প্রতিটা ঘরে "প্রথম কে কাটল" লিখে রাখা; পরে O(log n)-এ factorization। সরাসরি পরের ধাপ।
- **LeetCode — Count Primes** (