Problem link ও উৎস
- **Original source:** CP-Algorithms — Primality Tests
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Medium
- **Pattern:** beyond trial division
- **Basic idea inherited from:** 013 (Trial Division Primality)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক integer `n` দেওয়া আছে। বলতে হবে সেটা **prime** কি না — মানে n > 1 আর n-এর গুণনীয়ক শুধু 1 আর n নিজে (অন্য কোনো ভাগ নেই)।
Level 1-এ আমরা 2 থেকে n−1 পর্যন্ত সব সংখ্যা দিয়ে ভাগের চেষ্টা করেছিলাম। এই note-এ লক্ষ্য — সেই trial division-কে **যতটা সম্ভব শান দেওয়া** (√n পর্যন্ত, 6k±1 optimization), আর বোঝা **কোথায় এই পদ্ধতি থেমে যায়** (বড় n-এ) — যা 135-এর Miller-Rabin-এর প্রেরণা।
মনে রেখো — এই level CP-leaning, interview-optional। কিন্তু "কোন ধাপে কোন optimization যথেষ্ট, কখন আরও ভালো পদ্ধতি লাগে" — এই সিদ্ধান্তটা শেখার দারুণ উদাহরণ।
### Input ও output {#6-example-input-and-output}
```text
input n -> is_prime
----------------------------------------------------------------
1 -> False (1 prime নয় — সংজ্ঞা অনুযায়ী)
2 -> True (একমাত্র জোড় prime)
3 -> True
4 -> False (2×2)
37 -> True
91 -> False (7×13 — দেখতে prime মনে হয়!)
97 -> True
561 -> False (3×11×17 — Carmichael, কিন্তু trial division ধরে)
1000003 -> True (বড় prime)
```
খেয়াল করো: **1 prime নয়, 2 হলো একমাত্র জোড় prime** — দুটো গুরুত্বপূর্ণ edge case। আর 91-এর মতো সংখ্যা দেখতে prime মনে হলেও composite (7×13) — তাই চোখে আন্দাজ নয়, ভাগ করে দেখা। 561 (Carmichael number) এখানে trial division সহজে ধরে, কিন্তু 135-এ দেখব কেন এটা Fermat test-কে ফাঁকি দেয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমাকে একটা সংখ্যক চকলেট ঠিক সমান ভাগে কয়েকজনের মধ্যে বিলি করতে হবে — যদি কোনোভাবেই (1 জন বা সবাইকে একসাথে ছাড়া) সমান ভাগ না হয়, সংখ্যাটা prime।
এখন তুমি কি 2 থেকে n−1 জন পর্যন্ত প্রতিটা দল-আকার চেষ্টা করবে? অপচয়! একটু ভেবে দেখো:
- দল যদি n-এর অর্ধেকের বেশি বড় হয়, তাহলে প্রত্যেকে 1টার কম পাবে — তাই বড় দল দেখার দরকার নেই (√n-এর যুক্তি)।
- দল-আকার জোড় হলে আগেই জানো 2 দিয়ে ভাগ যায় কি না — তাই জোড় দল আলাদা করে দেখার দরকার নেই।
- বেশিরভাগ "সম্ভাব্য prime দল-আকার" 6-এর আশেপাশে একটা প্যাটার্নে পড়ে (6k±1) — বাকিগুলো এমনিতেই 2 বা 3 দিয়ে ভাগ যায়।
এই সব বাদ দিয়ে তুমি অনেক কম দল-আকার চেষ্টা করেই রায় দিতে পারো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **013 (Trial Division Primality)**। 013-তে আমরা ভাগ করে prime চেক করা শিখেছিলাম (হয়তো 2 থেকে n−1, বা √n পর্যন্ত)। 134 সেই একই trial division-কে √n + জোড়-বাদ + 6k±1 দিয়ে শান দেয় — মূল ধারণা এক, শুধু কম ভাজক।
আর এর উপরে দাঁড়াবে **135 (Miller-Rabin)** — যখন √n-ও বড্ড বেশি (n = 10¹⁸), তখন probabilistic/deterministic-witness পদ্ধতি। 134 দেখায় trial division-এর সীমা, যা 135-এর প্রয়োজনীয়তা বোঝায়। README-র recommended order-এ তাই 134 → 135 → 136 trilogy।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea তিনটা ধাপে শান দেওয়া:
- **√n পর্যন্ত যথেষ্ট** — n যদি composite হয়, তার অন্তত একটা গুণনীয়ক ≤ √n থাকবেই (কারণ যদি দুটো গুণনীয়কই √n-এর বড় হতো, গুণফল n ছাড়িয়ে যেত)। তাই 2 থেকে √n পর্যন্ত দেখলেই হলো।
- **জোড় বাদ** — 2 ছাড়া কোনো জোড় সংখ্যা prime নয়; তাই 2 আলাদা সামলে শুধু বিজোড় ভাজক দেখো।
- **6k ± 1** — 2 আর 3 ছাড়া সব prime `6k ± 1` আকারের (কারণ 6k, 6k+2, 6k+3, 6k+4 সবই 2 বা 3 দিয়ে ভাগ যায়)। তাই 5, 7 থেকে শুরু করে 6 করে লাফিয়ে শুধু `i` আর `i+2` দেখো — কাজ আরও এক-তৃতীয়াংশে নামে।
এই level CP-leaning হলেও মূল সুর সরল — "অপ্রয়োজনীয় ভাজক বাদ দাও"। কিন্তু এই সব optimization-এর পরেও মূল খরচ O(√n), যা n = 10¹⁸-এ অচল — সেখানেই 135 আসে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
013-এর সবচেয়ে সরল রূপ — **2 থেকে n−1 পর্যন্ত প্রতিটা সংখ্যা দিয়ে ভাগের চেষ্টা**:
```python
def is_prime_naive(n):
if n < 2:
return False
for d in range(2, n): # 2 থেকে n−1
if n % d == 0:
return False # ভাজক পেলাম -> composite
return True
```
ছোট n-এ (যেমন 37) নিখুঁত — কোনো ভাজক না পেলে prime। আমাদের শান-দেওয়া version-এর উত্তর এই naive version-এর সাথে মিলিয়ে যাচাই করব। শুরুর জন্য একদম পরিষ্কার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে প্রায় `n` বার। n বড় হলেই অচল:
```text
n = 37: ~35 বার ভাগ — তাৎক্ষণিক
n = 10⁶: ~10⁶ বার — ঠিক আছে (naive), √n দিলে মাত্র ~10³
n = 10¹²: naive ~10¹² বার অসম্ভব; √n দিলে ~10⁶ — চলে
n = 10¹⁸: √n দিলেও ~10⁹ বার — TLE! এখানেই Miller-Rabin লাগে
```
naive O(n) তো অনেক আগেই অচল; √n optimization O(√n)-এ নামায় (n = 10¹² পর্যন্ত চলে)। কিন্তু n = 10¹⁸-এ √n = 10⁹-ও বেশি — তখন trial division-এর সব শান দিয়েও হয় না, probabilistic পদ্ধতি (135) লাগে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **শুধু √n পর্যন্ত, আর শুধু সম্ভাব্য prime ভাজক দেখো।** ধাপ:
```text
1. n < 2 -> False; n == 2 বা 3 -> True
2. n % 2 == 0 বা n % 3 == 0 -> False (2, 3 আলাদা সামলানো শেষ)
3. i = 5 থেকে শুরু, i*i ≤ n পর্যন্ত:
যদি n % i == 0 বা n % (i+2) == 0 -> False
i += 6 (6k±1 লাফ)
4. কোনো ভাজক না পেলে -> True
```
কেন √n যথেষ্ট: composite n-এর ছোট গুণনীয়ক ≤ √n থাকবেই। কেন 6k±1: 2, 3 ছাড়া সব prime এই আকারের, তাই বাকি সব i এমনিতেই 2 বা 3 দিয়ে ভাগ্য — দেখার দরকার নেই। এতে trial division-এর কাজ প্রায় ⅓-এ নামে। তবু মূল order O(√n) — বড় n-এ 135 লাগবে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **composite হলে একটা ভাজক ≤ √n থাকবেই — তাই n−1 পর্যন্ত নয়, √n পর্যন্ত দেখলেই পুরো রায় দেওয়া যায়।**
brute force n−1 পর্যন্ত সব দেখছিল; tweak হলো — (ক) √n-এ থামো (অর্ধেকের বেশি গুণনীয়ক জোড়ায় আসে), (খ) জোড় ও 3-এর গুণিতক বাদ দিয়ে শুধু 6k±1 দেখো। O(n) থেকে O(√n)-এ, আর ধ্রুবক গুণনীয়কও ⅓-এ নেমে এল। দ্বিতীয় গভীর tweak: এই O(√n)-ও যখন বড্ড বেশি (10¹⁸), তখন একদম আলাদা চিন্তা (Fermat/Miller-Rabin) দরকার — সেটাই 135।
### ছবিতে বোঝা {#5-visual-explanation}
`is_prime(37)` — 6k±1 trial division-এ:
```text
n = 37, √37 ≈ 6.08, তাই i ≤ 6 পর্যন্ত দেখলেই হয়
ধাপ 0: 37 < 2? না। 37 == 2 বা 3? না।
37 % 2 == 0? না (বিজোড়)। 37 % 3 == 0? না।
6k±1 লুপ (i = 5 থেকে, i*i ≤ 37 মানে i ≤ 6):
i = 5: 37 % 5 = 2 (না), 37 % 7 = 2 (না) [i আর i+2 দেখলাম]
i = 11: 11*11 = 121 > 37 -> লুপ থামল
কোনো ভাজক পাওয়া যায়নি -> 37 PRIME ✓
তুলনায় composite — is_prime(91): (91 = 7 × 13)
i = 5: 91 % 5 = 1 (না), 91 % 7 = 0 -> ভাজক পেলাম! 91 COMPOSITE
```
লক্ষ করো — 37-এর জন্য মাত্র i = 5 (আর 7) দেখেই থেমে গেলাম, 2 থেকে 36 পর্যন্ত সব নয়। আর 91 ধরা পড়ল 7-এ, √91 ≈ 9.5-এর মধ্যেই।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`is_prime(91)` — 6k±1 (91 = 7 × 13):
| step | কী চেক করছি | ফল |
| --- | --- | --- |
| 1 | 91 < 2? | না |
| 2 | 91 == 2 বা 3? | না |
| 3 | 91 % 2 == 0? | না (বিজোড়) |
| 4 | 91 % 3 == 0? | না (9+1=10, 3 দিয়ে ভাগ যায় না) |
| 5 | i = 5: 5·5 = 25 ≤ 91? হ্যাঁ | চেক করি |
| 6 | 91 % 5 == 0? | না (ভাগশেষ 1) |
| 7 | 91 % 7 == 0? (i+2 = 7) | **হ্যাঁ!** → return False |
চূড়ান্ত: **False** (composite, কারণ 7 ভাগ করে)। লক্ষ করো — i = 5-এর ধাপেই i+2 = 7 দিয়ে ধরা পড়ল, √91 ≈ 9.5-এর অনেক আগে।
আরেকটা: `is_prime(37)` — কোনো ভাজক নেই, i = 5-এ (5, 7 কোনোটাই ভাগ করে না), পরের i = 11-এ 11·11 = 121 > 37, লুপ থামে → **True** (prime)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def is_prime(n):
"""trial division — √n পর্যন্ত, জোড়-বাদ, 6k±1 optimization। O(√n)।"""
if n < 2:
return False
if n < 4:
return True # 2, 3 prime
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6 # 6k±1: শুধু i আর i+2 দেখি
return True
# --- ছোট test গুলো (সব pass করা উচিত) ---
def is_prime_naive(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return True
# শান-দেওয়া বনাম naive — 0..2000 সব মেলাও
for n in range(0, 2001):
assert is_prime(n) == is_prime_naive(n), f"is_prime({n}) অমিল"
# জানা small primes
PRIMES_UNDER_30 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
for n in range(0, 30):
assert is_prime(n) == (n in PRIMES_UNDER_30), f"small {n} অমিল"
# edge cases
assert is_prime(1) is False
assert is_prime(2) is True
assert is_prime(0) is False
# composite যেগুলো দেখতে prime মনে হয়
assert is_prime(91) is False # 7×13
assert is_prime(143) is False # 11×13
assert is_prime(561) is False # 3×11×17 (Carmichael)
# বড় prime ও composite
assert is_prime(1000003) is True
assert is_prime(1000000007) is True # CP-র প্রিয় mod, prime
assert is_prime(1000000) is False
assert is_prime(999983) is True # 10⁶-এর নিচে সবচেয়ে বড় prime
# prime গোনা: 100-এর নিচে ঠিক 25টা prime
assert sum(1 for n in range(2, 100) if is_prime(n)) == 25
print(is_prime(37)) # True
print(is_prime(91)) # False
print(is_prime(1000000007)) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def is_prime(n):
if n < 2:
return False
if n < 4:
return True
```
n < 2 (0, 1, negative) prime নয়। 2 আর 3 (n < 4) prime — আলাদা সামলে নিচ্ছি, যাতে 6k±1 লুপ পরিষ্কার থাকে।
```
if n % 2 == 0 or n % 3 == 0:
return False
```
2 আর 3 ইতিমধ্যে handle করা; এখন 2 বা 3-এর যেকোনো গুণিতক composite। এই দুই বাদ দিলে বাকি সব সম্ভাব্য prime 6k±1 আকারের।
```
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
```
i = 5, 11, 17, ... (6k−1), আর i+2 = 7, 13, 19, ... (6k+1) — এই দুই আকারই বাকি সব prime ও তাদের গুণিতক ঢেকে দেয়। `i*i <= n` মানে √n পর্যন্ত। কোনোটা ভাগ করলে composite।
```
return True
```
√n পর্যন্ত কোনো ভাজক না পেলে n prime।
বাকি test অংশে শান-দেওয়া বনাম naive (0..2000), small prime set, edge case (0, 1, 2), দেখতে-prime composite (91, 143, 561), বড় prime/composite, আর "100-এর নিচে 25টা prime" সব যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
True
False
True
সব test pass!
```
`is_prime(37)` → True (কোনো ভাজক নেই, √37-এর মধ্যে)। `is_prime(91)` → False (7 ভাগ করে, section 11-এর dry run-এর সাথে মিল)। `is_prime(1000000007)` → True (CP-র প্রিয় mod, সত্যিই prime)। তার আগে 0..2000-এর সব মান naive-এর সাথে মিলেছে, সব edge case ও জানা মান pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√n)** — লুপ i = 5 থেকে √n পর্যন্ত, 6 করে লাফায়, তাই প্রায় √n / 6 বার iteration (ধ্রুবক গুণনীয়ক ছোট)। naive-এর O(n)-এর তুলনায় বিশাল উন্নতি (n = 10¹²-এ 10¹² বনাম 10⁶)। কিন্তু n = 10¹⁸-এ √n = 10⁹ — এটাও বেশি, তখন O(log³ n)-জাতীয় Miller-Rabin (135) লাগে।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো array নেই, শুধু গুটিকয় variable (i, n)। একটামাত্র সংখ্যার primality-র জন্য এটাই যথেষ্ট। (অনেক সংখ্যার primality একসাথে চাইলে sieve-এ O(n) array — আলাদা বিষয়, 137-এ।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **1-কে prime ভাবা** — 1 prime **নয়** (সংজ্ঞায় prime > 1, ঠিক দুটো গুণনীয়ক)। n < 2 → False আগে চেক করো।
2. **√n-এর বদলে n−1 পর্যন্ত যাওয়া** — অপ্রয়োজনীয় ধীর; composite-এর ভাজক ≤ √n থাকবেই, তাই `i*i <= n`।
3. **`i*i <= n`-এর বদলে `i <= sqrt(n)` (float)** — float-এ round-off ভুল হতে পারে (বড় n-এ); integer তুলনা `i*i <= n` নিরাপদ।
4. **6k±1-এ i+2 ভুলে যাওয়া** — শুধু i দেখলে (i+2 বাদ) কিছু prime-এর গুণিতক মিস হবে; দুটোই দেখতে হবে।
5. **বড় n-এও trial division-ই যথেষ্ট ভাবা** — n = 10¹⁸-এ O(√n) অচল; তখন Miller-Rabin (135)। কোন মাপে কোন পদ্ধতি — সেটা বোঝা জরুরি।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Primes / প্রচুর prime query** (