Problem link ও উৎস
- Original source: Classic beginner exercise
- Platform: Classic exercise
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Easy
- Pattern: repeated prime check
- Basic idea inherited from: 013 (Check Prime)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যা `N` দেওয়া আছে। 2 থেকে `N` পর্যন্ত যত prime আছে, **সবগুলো** একটা তালিকায় বের করতে হবে।
যেমন `N = 20` হলে উত্তর: `[2, 3, 5, 7, 11, 13, 17, 19]`।
013-এ আমরা একটা সংখ্যা prime কিনা দেখতাম; এখানে সেই কাজটাই 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় চালিয়ে যারা prime, তাদের জড়ো করব।
### Input ও output {#6-example-input-and-output}
```text
primes_upto(N)
-----------------------------------------
primes_upto(20) -> [2, 3, 5, 7, 11, 13, 17, 19]
primes_upto(2) -> [2] (সবচেয়ে ছোট prime)
primes_upto(1) -> [] <-- 2-এর নিচে কোনো prime নেই
primes_upto(0) -> []
primes_upto(13) -> [2, 3, 5, 7, 11, 13] (13 নিজেও ধরা পড়ে, ≤ N)
```
দুটো edge case: **N < 2 হলে খালি তালিকা** (2-ই সবচেয়ে ছোট prime, তার নিচে কেউ নেই), আর **N নিজে prime হলে সে-ও তালিকায়** (যেমন N = 13)। তাই loop-এ N পর্যন্ত ধরা (`range(2, N+1)`) জরুরি।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **বড় ঝুড়ি ভর্তি ফল**, আর তোমাকে শুধু **পাকা** ফলগুলো আলাদা করতে হবে।
- ঝুড়ির ফল = 2 থেকে N পর্যন্ত সব সংখ্যা
- "এই ফলটা পাকা?" পরীক্ষা = `is_prime(num)` (013-এর কাজ)
- পাকা হলে আলাদা ঝুড়িতে রাখা = `result.append(num)`
তুমি এক-একটা ফল হাতে নিয়ে পরীক্ষা করছ, পাকা হলে সরিয়ে রাখছ — শেষে আলাদা ঝুড়িতে শুধু পাকা ফল (prime)। এই "এক-এক করে পরীক্ষা" পদ্ধতি কাজ করে, কিন্তু ফল অনেক হলে সময় লাগে — তখন মনে প্রশ্ন জাগে, "এক-একটা না দেখে কি একসাথে বাছা যায়?" সেই প্রশ্নের উত্তরই 015 (Sieve)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **013 (Check Prime)** থেকে — আক্ষরিক অর্থেই এটা 013-কে একটা loop-এ মুড়ে দেওয়া।
```
013: is_prime(n) -> একটা সংখ্যা prime?
014: for num in 2..N: -> প্রতিটা সংখ্যায় 013 ডাকো,
if is_prime(num): ... prime হলে জড়ো করো
```
মানে 013 ছিল একক প্রশ্ন, 014 হলো সেই প্রশ্ন বারবার করে উত্তর জড়ো করা। এটা একই inheritance-সুর: একটা ছোট নির্ভরযোগ্য কাজ (prime check) পেয়ে গেলে, তাকে loop-এ বসিয়েই বড় কাজ (সব prime তালিকা) হয়ে যায়। 013-এর check ভুল থাকলে এখানে পুরো তালিকাই ভুল হবে — তাই ভিত্তিটা পোক্ত হওয়া জরুরি।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
কোনো নতুন গণিত নয় — মূল idea হলো **repeated prime check**: 013-এর `is_prime` কে একটা loop-এ বসিয়ে 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় ডাকো, যেটা prime সেটাকে তালিকায় রাখো।
```
result = []
2 থেকে N পর্যন্ত প্রতিটা num:
যদি is_prime(num):
result-এ num যোগ করো
return result
```
এটুকুই। আসল শেখা এখানে algorithm-এ নয়, বরং **খরচ** নিয়ে ভাবায় — প্রতিটা সংখ্যার জন্য আলাদা √n check চালালে মোট কত কাজ হয়, আর সেটা কমানো যায় কিনা (Section 8 ও 18)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল — 013-এর `is_prime` কে loop-এ বসিয়ে প্রতিটা সংখ্যা যাচাই:
```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_upto_brute(N):
return [num for num in range(2, N + 1) if is_prime(num)]
```
একদম পরিষ্কার, 013 জানলে এক মিনিটে লেখা। 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় `is_prime` ডাকছি, যারা prime তাদের তালিকায় নিচ্ছি। ছোট-মাঝারি N-এ (যেমন 10⁴, 10⁵) এটাই যথেষ্ট।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
প্রতিটা সংখ্যার জন্য আলাদা √num check — মোট খরচ যোগ হয়ে বড় হয়:
- N পর্যন্ত প্রতিটা সংখ্যায় ≈ √num কাজ, মোট ≈ `√2 + √3 + ... + √N` ≈ **O(N√N)**। N = 10⁶ হলে ≈ 10⁹ কাজ — ধীর, প্রায় TLE।
```text
N = 1000000 হলে:
এক-এক করে check : O(N√N) ≈ 10^9 কাজ -> ধীর
Sieve (015) : O(N log log N) ≈ ~3×10^6 -> অনেক দ্রুত
```
কোথায় অপচয়? একই composite সংখ্যা (যেমন 30) আমরা বারবার "ভাগ যায় কিনা" পরীক্ষা করি — অথচ 30 যে 2, 3, 5-এর গুণিতক, সেটা একবার জানলেই হতো। **এই বারবার পরীক্ষার অপচয়ই Sieve-এর জন্ম দেয়:** prime খুঁজে না বের করে, composite-দের একসাথে কেটে ফেলা (015-এ পুরোটা)। এই note-এর সবচেয়ে দামি উপলব্ধি এটাই।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
দুটো স্তরে উন্নতি:
**(ক) ছোট optimization — 2 আলাদা, পরে শুধু বিজোড়:** 2 ছাড়া সব জোড় সংখ্যা বাদ, তাই check করার সংখ্যা প্রায় অর্ধেক:
```python
def primes_upto(N):
if N < 2:
return []
result = [2]
for num in range(3, N + 1, 2): # শুধু বিজোড়
if is_prime(num):
result.append(num)
return result
```
**(খ) আসল বড় লাফ — Sieve (পরের problem 015):** এক-একটা সংখ্যা check না করে, 2 থেকে শুরু করে প্রতিটা prime-এর **সব গুণিতক একসাথে কেটে ফেলা**; যারা বেঁচে থাকে তারাই prime। এটা O(N log log N) — N বড় হলে আকাশ-পাতাল দ্রুত। 014 হলো সেই দরজার সামনে দাঁড়ানো; ভেতরে ঢুকব 015-এ।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় দুই ভাগে:
- **এই problem-এর জন্য:** "একটা সংখ্যা prime?" উত্তর জানা থাকলে "সব prime?" শুধু একটা loop + জড়ো করা — নতুন কিছু ভাবার নেই, পুরোনো হাতিয়ার পুনর্ব্যবহার।
- **পরের দিকে তাকানো tweak (আসল আহা):** **prime খুঁজো না — composite কেটে ফেলো।** এক-একটা সংখ্যায় বারবার ভাগের পরীক্ষা চালানোর বদলে, প্রতিটা prime-এর গুণিতক একবারে দাগিয়ে দাও; যা অদাগি থাকে তা-ই prime। এই দৃষ্টিভঙ্গি-বদল (search → mark) Sieve-এর প্রাণ, আর precompute-জাতীয় বহু problem-এ ফিরবে।
এই note-এর মূল শিক্ষা তাই একটা সমাধান নয়, একটা **প্রশ্ন**: "একই কাজ কি বারবার করছি? তবে কি একসাথে করা যায়?"
### ছবিতে বোঝা {#5-visual-explanation}
`N = 20`-এ এক-এক করে check চলছে, পাকা (prime) গুলো ডান ঝুড়িতে জমছে:
```text
num : 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
is_prime?
P P . P . P . . . P . P . . . P . P .
| | | | | | | |
v v v v v v v v
result ঝুড়ি: [2, 3, 5, 7, 11, 13, 17, 19]
P = prime (তালিকায় গেল), . = composite (বাদ)
```
লক্ষ করো — প্রতিটা num-এর জন্য 013-এর পুরো √num check আলাদাভাবে চলছে (নিচে দেখব এটাই খরচের জায়গা)।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`N = 10` দিয়ে Section 9-এর version (2 আলাদা, পরে বিজোড়) হাতে চালাই:
| ধাপ | num | is_prime(num)? | result (পরে) |
| --- | --- | --- | --- |
| শুরু | — | — | [2] |
| 1 | 3 | True (3 prime) | [2, 3] |
| 2 | 5 | True | [2, 3, 5] |
| 3 | 7 | True | [2, 3, 5, 7] |
| 4 | 9 | False (9 = 3×3) | [2, 3, 5, 7] |
loop `range(3, 11, 2)` শেষ (3, 5, 7, 9 দেখা হলো)। চূড়ান্ত **[2, 3, 5, 7]** — ঠিক 10 পর্যন্ত সব prime। লক্ষ করো 9-এ `is_prime` False ফিরিয়েছে (013-এর √9 check-এ 3 ভাগ করল), তাই বাদ। আর জোড় সংখ্যা (4, 6, 8, 10) আমরা দেখিইনি — 2 আগেই তালিকায়, বাকি জোড়রা prime নয় বলে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def is_prime(n):
"""013-এর √n prime check (পুনর্ব্যবহার)।"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
def primes_upto(N):
"""2 থেকে N পর্যন্ত সব prime-এর তালিকা (repeated check)।"""
if N < 2:
return []
result = [2]
for num in range(3, N + 1, 2): # 2 আলাদা, এরপর শুধু বিজোড়
if is_prime(num):
result.append(num)
return result
def primes_upto_brute(N):
"""একই উত্তর, সরল সব-সংখ্যা check — যাচাইয়ের জন্য।"""
return [num for num in range(2, N + 1) if is_prime(num)]
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert primes_upto(20) == [2, 3, 5, 7, 11, 13, 17, 19]
assert primes_upto(2) == [2] # সবচেয়ে ছোট prime
assert primes_upto(1) == [] # 2-এর নিচে কিছু নেই
assert primes_upto(0) == []
assert primes_upto(-5) == []
assert primes_upto(13) == [2, 3, 5, 7, 11, 13] # N নিজে prime, ধরা পড়ে
# দুই পদ্ধতি সব N-এ মেলে কিনা
for N in range(0, 100):
assert primes_upto(N) == primes_upto_brute(N)
# 30 পর্যন্ত prime সংখ্যা ঠিক 10টা
assert len(primes_upto(30)) == 10
print(primes_upto(20)) # [2, 3, 5, 7, 11, 13, 17, 19]
print(primes_upto(2)) # [2]
print(primes_upto(1)) # []
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def is_prime(n):
...
```
013-এর সেই √n prime check, হুবহু পুনর্ব্যবহার — 2 আলাদা, জোড় বাদ, তারপর বিজোড় ভাজক দিয়ে √n পর্যন্ত। 014-এর পুরো সঠিকতা এই function-এর উপর দাঁড়িয়ে।
```
if N < 2:
return []
```
N 2-এর নিচে হলে কোনো prime নেই — খালি তালিকা ফেরাই (edge case)।
```
result = [2]
for num in range(3, N + 1, 2):
if is_prime(num):
result.append(num)
```
2-কে আগে তালিকায় রাখি (একমাত্র জোড় prime), তারপর `range(3, N+1, 2)` দিয়ে শুধু **বিজোড়** সংখ্যা (3, 5, 7...) ঘুরি — জোড়রা 2 ছাড়া prime নয় বলে বাদ। প্রতিটা prime হলে তালিকায় যোগ। `N + 1` দিয়ে N-কেও ধরছি (N নিজে prime হলে যেন বাদ না পড়ে)।
```
def primes_upto_brute(N):
return [num for num in range(2, N + 1) if is_prime(num)]
```
তুলনার version — কোনো 2-আলাদা চাল নয়, সরাসরি 2 থেকে N সব সংখ্যা check। ধীর হলেও সহজ, তাই reference হিসেবে ভালো।
`for N in range(0, 100)` loop দুই পদ্ধতিকে 100টা N-এ মিলিয়ে যাচাই করে (সোনার নিয়ম)। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[2, 3, 5, 7, 11, 13, 17, 19]
[2]
[]
সব test pass!
```
তিনটা লাইন তিনটা `print` থেকে: `primes_upto(20)` → 20 পর্যন্ত 8টা prime, `primes_upto(2)` → শুধু [2], `primes_upto(1)` → খালি তালিকা (edge case)। তার আগে সব `assert` — নির্দিষ্ট কেস, 0..99 জুড়ে দুই পদ্ধতির মিল, আর 30 পর্যন্ত গোনা — চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` মানে তালিকা সব ক্ষেত্রে সঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(N√N)** — 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় ≈ √num কাজ (013-এর check), যোগ করলে প্রায় `N × √N`। N = 10⁴-এ ঠিকঠাক, কিন্তু N = 10⁶-এ (~10⁹ কাজ) ধীর। তুলনায় Sieve (015) O(N log log N) — অনেক দ্রুত। (2-আলাদা optimization ধ্রুবক গুণনীয়ক অর্ধেক করে, কিন্তু Big-O একই থাকে।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(π(N))** — যেখানে π(N) মানে N পর্যন্ত prime সংখ্যা (output তালিকার আকার)। prime check নিজে O(1) extra space নেয়; মূল জায়গা যায় ফলাফল তালিকায়। (সব prime ফেরত দিতেই হবে, তাই এটা অনিবার্য।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`range(2, N)` দিয়ে N বাদ** — N নিজে prime হলে (যেমন 13) তালিকায় থাকা উচিত; `range(2, N+1)` লাগে, নাহলে শেষ prime ফসকায়।
2. **N < 2-এ খালি তালিকা না দেওয়া** — `primes_upto(1)` বা `primes_upto(0)` যেন `[]` ফেরায়; না হলে loop বা index-এ গোলমাল।
3. **`is_prime`-এ 1 বা 2-এর ভুল ছড়িয়ে পড়া** — 013-এর check-এ 1-কে prime ধরলে বা 2-কে বাদ দিলে, এখানে পুরো তালিকা ভুল হবে। ভিত্তি function ঠিক রাখো।
4. **বড় N-এ এই পদ্ধতিতে আটকে থাকা** — N বিশাল হলে repeated check TLE দেবে; তখন Sieve (015)-এ যাও। "এক-এক করে check" সবসময়ের সমাধান নয়।
5. **জোড় optimization-এ 2 ভুলে যাওয়া** — শুধু বিজোড় loop করলে 2-কে আলাদা করে `result`-এ আগে রাখতে ভুলো না, নাহলে 2 তালিকা থেকে বাদ পড়বে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **015 — Sieve of Eratosthenes** (এই repo) — এই problem-এর সরাসরি উত্তর-উন্নয়ন: এক-এক করে check না করে composite একসাথে কেটে ফেলা, O(N log log N)। সম্পর্কিত: **CP-Algorithms — Sieve** (