Problem link ও উৎস
- Original source: Classic beginner exercise
- Platform: Classic exercise
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Easy
- Pattern: trial division
- Basic idea inherited from: 012 (Count Factors)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer `n` দেওয়া আছে। বলতে হবে সেটা **prime** (মৌলিক সংখ্যা) কিনা।
মনে করিয়ে দিই: prime মানে এমন সংখ্যা যার ঠিক **দুটো** factor — 1 আর সে নিজে। যেমন 2, 3, 5, 7, 11, 13... এরা prime। আর 4 (= 2×2), 6 (= 2×3), 9 (= 3×3) — এদের বাড়তি factor আছে, তাই এরা **composite** (যৌগিক)।
বিশেষ সতর্কতা: **1 prime নয়** (তার factor মোটে একটা — শুধু নিজে), আর **2 হলো একমাত্র জোড় prime**।
### Input ও output {#6-example-input-and-output}
```text
is_prime(n)
--------------------------
is_prime(2) -> True (একমাত্র জোড় prime)
is_prime(7) -> True
is_prime(97) -> True
is_prime(1) -> False <-- সাবধান! 1 prime নয়
is_prime(0) -> False
is_prime(-7) -> False (negative prime হয় না)
is_prime(4) -> False (2×2)
is_prime(91) -> False (7×13 — ছদ্মবেশী!)
```
তিনটা দামি edge case: **1 → False** (factor মোটে একটা), **2 → True** (একমাত্র জোড় prime), আর **91 → False** (দেখতে prime, আসলে 7×13 — এজন্যই চোখের আন্দাজ নয়, check লাগে)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো prime হলো একটা **নিঃসঙ্গ ইট** — তাকে কোনোভাবেই ছোট ছোট সমান ভাগে (1 আর নিজে ছাড়া) ভাঙা যায় না।
- 7টা মার্বেল — তুমি যতই চেষ্টা করো, সমান কয়েক সারিতে সাজাতে পারবে না (1 সারি 7টা, বা 7 সারি 1টা ছাড়া) → **prime**
- 12টা মার্বেল — দিব্যি সাজানো যায়: 2×6, 3×4, 4×3... → **composite**
trial division হলো তোমার পরীক্ষা: "2 সারিতে সাজানো যায়? 3 সারিতে? ..." — √n পর্যন্ত কোনো সাজানো না গেলে নিশ্চিত, এটা নিঃসঙ্গ ইট, prime।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **012 (Count Factors)** থেকে।
012-এ আমরা √n পর্যন্ত খুঁজে **সব** factor গুনতাম। 013-এ সেই একই √n loop, কিন্তু এবার গোনা নয় — শুধু **একটা** বাড়তি factor আছে কিনা সেটুকু জানলেই চলে। প্রথম ভাজক পেলেই থামি (early exit), কারণ একটা বাড়তি factor মানেই আর prime নয়।
```
012: for i in √n: factor হলে গুনতে থাকো (সব দেখো)
013: for i in √n: factor পেলেই থামো -> composite (একটাই যথেষ্ট)
```
আসলে prime = "ঠিক 2টা factor" — তাই 013 হলো 012-এরই বিশেষ প্রশ্ন: factor সংখ্যা ঠিক 2 কিনা। কিন্তু গুনে শেষ করার দরকার নেই; 2 থেকে √n-এ একটাও ভাজক না থাকলেই prime। 012-এর √n যুক্তি না বুঝলে এখানে "কেন √n যথেষ্ট" আবছা থাকবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **trial division**: 2 থেকে √n পর্যন্ত কোনো সংখ্যা `n`-কে ভাগ করে কিনা দেখো। একজনও পেলে `n` composite; কেউ না পেলে prime।
```
যদি n < 2: prime নয়
2 থেকে √n পর্যন্ত প্রতিটা i:
যদি n % i == 0: -> ভাগ মিলে গেল -> composite (return False)
কেউ ভাগ না করলে: -> prime (return True)
```
কেন √n পর্যন্তই যথেষ্ট? 012-এর সেই জোড়ার যুক্তি — `n`-এর কোনো ভাজক থাকলে তার জোড়ার একজন √n-এর এপারে অবশ্যই থাকবে। তাই √n পর্যন্ত কাউকে না পেলে নিশ্চিত — ওপারেও কেউ নেই, সংখ্যাটা prime।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল ভাবনা — 2 থেকে `n-1` পর্যন্ত **প্রতিটা** সংখ্যা দেখি, কেউ ভাগ করে কিনা:
```python
def is_prime_brute(n):
if n < 2:
return False
for i in range(2, n): # 2 থেকে n-1 সব দেখো
if n % i == 0:
return False # একজন পেলেই composite
return True
```
এটা একদম প্রত্যক্ষ — prime-এর সংজ্ঞা ("1 আর নিজে ছাড়া কেউ ভাগ করে না") সরাসরি code-এ। 2 থেকে n পর্যন্ত সবাইকে জিজ্ঞেস করি "তুমি কি ভাগ করো?", কেউ হ্যাঁ বললেই composite।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা — loop ঘোরে প্রায় **n বার**:
- `n` যদি বড় prime হয় (যেমন 1,000,000,007), তাহলে কেউই ভাগ করে না, তাই loop পুরো প্রায় 100 কোটি বার ঘুরে তবে `True` ফেরায় — interview-তে Time Limit Exceeded।
```text
n = 1000000007 (বড় prime) হলে:
brute O(n) : ~10^9 বার loop -> অসম্ভব ধীর
√n O(√n) : ~31623 বার loop -> চোখের নিমেষে
```
মূল অপচয়: √n-এর ওপারে খোঁজা **অপ্রয়োজনীয়**। কারণ যদি √n পর্যন্ত কোনো ভাজক না থাকে, তবে ওপারেও থাকবে না (012-এর জোড়ার যুক্তি — কোনো ভাজকের জোড়ার একজন তো √n-এর এপারে থাকতই)। তাই n-এর বদলে √n পর্যন্ত খুঁজলেই হয়, কাজ নাটকীয়ভাবে কমে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
√n পর্যন্ত trial division, প্রথম ভাজক পেলেই থামো:
```python
def is_prime(n):
if n < 2:
return False # 0, 1, negative — prime নয়
i = 2
while i * i <= n: # √n পর্যন্ত (i*i, sqrt এড়িয়ে)
if n % i == 0:
return False # একটা ভাজক = composite, সঙ্গে সঙ্গে শেষ
i += 1
return True # কেউ ভাগ করল না = prime
```
আগের মতোই `i * i <= n` (integer, float-ভুল এড়ায়)। আরেকটা ছোট optimization — 2 আলাদা সামলে তারপর শুধু বিজোড় i দেখা (জোড় সংখ্যা 2 ছাড়া আর prime-কে ভাগ করতে পারে না), তাতে কাজ আরও অর্ধেক। নিচের solution-এ সেই version-ও আছে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় দুই স্তরে:
- **√n যথেষ্ট:** ভাজক জোড়ায় আসে, প্রতি জোড়ার ছোট জন ≤ √n — তাই √n পর্যন্ত কাউকে না পেলে নিশ্চিত prime। (012 থেকে সরাসরি ধার করা।)
- **early exit:** prime check-এ গুনে শেষ করার দরকার নেই — **প্রথম** ভাজক পেলেই উত্তর "composite", তখনই return। শুধু prime-এর ক্ষেত্রেই পুরো √n ঘুরতে হয়।
আর একটা ব্যবহারিক tweak: 2 আলাদা handle করে এরপর শুধু বিজোড় ভাজক (3, 5, 7, ...) পরীক্ষা — জোড় সংখ্যা দিয়ে ভাগের চেষ্টা বৃথা (2-ই তো ধরা পড়ে যেত)। এই "2 আলাদা, পরে শুধু odd" চিন্তাটা sieve-এও কাজে লাগবে।
### ছবিতে বোঝা {#5-visual-explanation}
`97` (prime) আর `91` (ছদ্মবেশী composite) — দুটোতে trial division পাশাপাশি দেখো:
```text
n = 97 (prime): √97 ≈ 9.8, তাই i = 2..9 দেখি
97 % 2 = 1 97 % 3 = 1 97 % 4 = 1 97 % 5 = 2
97 % 6 = 1 97 % 7 = 6 97 % 8 = 1 97 % 9 = 7
কেউ ভাগ করল না -> PRIME ✓
n = 91 ("দেখতে prime"): √91 ≈ 9.5, i = 2..9
91 % 2 = 1 91 % 3 = 1 91 % 4 = 3 91 % 5 = 1
91 % 6 = 1 91 % 7 = 0 <-- ধরা পড়ল! 91 = 7 × 13
-> COMPOSITE ✗ (prime নয়, যদিও দেখতে তেমন)
```
এক বাক্যে: **√n পর্যন্ত একটাও ভাগ না মিললে prime; একটা মিললেই composite।**
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 91` দিয়ে √n version হাতে চালাই। `i * i <= 91` মানে i যাবে 2..9 (10×10=100 > 91):
| i | i*i | i*i <= 91? | 91 % i | ভাগ যায়? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- |
| 2 | 4 | হ্যাঁ | 1 | না | চালিয়ে যাও |
| 3 | 9 | হ্যাঁ | 1 | না | চালিয়ে যাও |
| 4 | 16 | হ্যাঁ | 3 | না | চালিয়ে যাও |
| 5 | 25 | হ্যাঁ | 1 | না | চালিয়ে যাও |
| 6 | 36 | হ্যাঁ | 1 | না | চালিয়ে যাও |
| 7 | 49 | হ্যাঁ | **0** | **হ্যাঁ** | **return False** |
i = 7-এ `91 % 7 == 0` (91 = 7×13) → সঙ্গে সঙ্গে **False**, loop আর চলে না। 91 composite। মিলিয়ে দেখো — 91 দেখতে prime-এর মতো হলেও নয়, এজন্যই trial division লাগে। আর `n = 97` হলে i = 2..9 কেউ ভাগ করত না, i = 10-এ `100 > 97` → loop শেষ → **True**।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def is_prime(n):
"""n prime হলে True, নাহলে False — O(√n) trial division।"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False # 2 ছাড়া কোনো জোড় prime নয়
i = 3
while i * i <= n:
if n % i == 0:
return False # প্রথম ভাজকেই composite
i += 2 # শুধু বিজোড় ভাজক দেখি
return True
def is_prime_brute(n):
"""একই উত্তর, সরল O(n) — যাচাইয়ের জন্য।"""
if n < 2:
return False
return all(n % i != 0 for i in range(2, n))
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert is_prime(2) is True # একমাত্র জোড় prime
assert is_prime(3) is True
assert is_prime(7) is True
assert is_prime(97) is True
assert is_prime(1) is False # 1 prime নয় — দামি edge case
assert is_prime(0) is False
assert is_prime(-7) is False # negative prime নয়
assert is_prime(4) is False # 2×2
assert is_prime(91) is False # 7×13 — ছদ্মবেশী
assert is_prime(9) is False # 3×3
# সরল আর চালাক — দুই পদ্ধতি সব ছোট n-এ মেলে কিনা
for n in range(-5, 300):
assert is_prime(n) == is_prime_brute(n)
# প্রথম কয়েকটা prime ঠিকঠাক ধরা পড়ে
primes_upto_30 = [n for n in range(2, 31) if is_prime(n)]
assert primes_upto_30 == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(is_prime(2)) # True
print(is_prime(97)) # True
print(is_prime(91)) # False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
if n < 2:
return False
```
**প্রথম রক্ষাকবচ।** 0, 1, আর সব negative সংখ্যা — কোনোটাই prime নয় (prime ≥ 2)। এটা 1-এর ফাঁদ আটকায়।
```
if n == 2:
return True
if n % 2 == 0:
return False
```
2-কে আলাদা করে True বলি (একমাত্র জোড় prime), তারপর বাকি সব জোড় সংখ্যা সরাসরি False — কারণ তারা 2 দিয়ে ভাগ যায়, prime হতে পারে না। এতে পরে শুধু বিজোড় ভাজক দেখলেই চলে।
```
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
```
চেনা √n loop, কিন্তু `i` 3 থেকে শুরু করে **2 করে বাড়ছে** (3, 5, 7, 9...) — শুধু বিজোড় ভাজক দেখি, কারণ জোড় ভাজক আগেই বাদ পড়েছে। `i * i <= n` দিয়ে √n পর্যন্ত (integer compare)। কোনো ভাজক পেলেই **সঙ্গে সঙ্গে** False — early exit।
```
return True
```
পুরো √n পর্যন্ত কেউ ভাগ করল না — তাই prime।
`for n in range(-5, 300)` loop চালাক version-কে সরল version-এর সাথে 305টা সংখ্যায় (negative সহ) মিলিয়ে যাচাই করে — সোনার নিয়ম। আর prime তালিকার assert নিশ্চিত করে প্রথম 10টা prime ঠিক ধরা পড়ছে। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
True
True
False
সব test pass!
```
তিনটা লাইন তিনটা `print` থেকে: `is_prime(2)` → True (একমাত্র জোড় prime), `is_prime(97)` → True, `is_prime(91)` → False (7×13)। তার আগে সব `assert` — edge case (0, 1, negative, 4, 9, 91), −5..299 জুড়ে দুই পদ্ধতির মিল, আর 30 পর্যন্ত prime তালিকা — চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` মানে √n চালাক version সব ক্ষেত্রে সঠিক।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এও `%` আছে, কিন্তু integer division নেই — তাই `i * i <= n` দিয়েই √n সীমা মাপি (`Math.sqrt` এড়িয়ে)।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function isPrime(n) {
if (n < 2) return false; // 0, 1, negative — prime নয়
if (n === 2) return true; // একমাত্র জোড় prime
if (n % 2 === 0) return false; // বাকি জোড় সব composite
for (let i = 3; i * i <= n; i += 2) { // শুধু বিজোড় ভাজক
if (n % i === 0) return false; // প্রথম ভাজকেই composite
}
return true;
}
// ---- test cases (file-এর example + edge case) ----
assert(isPrime(2) === true, "2 একমাত্র জোড় prime");
assert(isPrime(7) === true, "7");
assert(isPrime(97) === true, "97");
assert(isPrime(1) === false, "1 prime নয়");
assert(isPrime(0) === false, "0");
assert(isPrime(-7) === false, "negative");
assert(isPrime(4) === false, "2x2");
assert(isPrime(91) === false, "91 = 7x13 ছদ্মবেশী");
assert(isPrime(9) === false, "3x3");
// 2..30 পর্যন্ত prime তালিকা ঠিক ধরা পড়ে
const primes = [];
for (let k = 2; k <= 30; k++) if (isPrime(k)) primes.push(k);
assert(JSON.stringify(primes) === JSON.stringify([2, 3, 5, 7, 11, 13, 17, 19, 23, 29]), "list");
console.log("সব JS test pass!");
```
> **JS টীকা:** integer division নেই, তাই √n চেক `i * i <= n` (integer) দিয়ে রাখো — `Math.sqrt` float rounding-এ বড় n-এ ভাজক ফসকাতে পারে। `n % 2` negative-এ ঝামেলা করে না এখানে, কারণ `n < 2` আগেই negative আটকায়।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function isPrime(n: number): boolean {
if (n < 2) return false;
if (n === 2) return true;
if (n % 2 === 0) return false;
for (let i = 3; i * i <= n; i += 2) {
if (n % i === 0) return false;
}
return true;
}
// table-driven test: [input, expected]
function expect