013 — Check Prime

012-এ তুমি √n পর্যন্ত খুঁজে factor গুনেছ। আজ সেই একই √n loop, কিন্তু গোনার দরকার নেই — শুধু একটা প্রশ্ন: "1 আর নিজে ছাড়া আর কেউ কি ভাগ করে?" একজনও পেলেই সংখ্যাটা prime নয়। এটাই prime check, পুরো গণিত-জগতের অন্যতম মৌলিক প্রশ্ন। সাথে কয়েকটা বিখ্যাত ফাঁদ — 1 prime নয়, 2 একমাত্র জোড় prime, আর 91-এর মতো "ছদ্মবেশী" সংখ্যা। ধীরে যাও, কেন √n যথেষ্ট সেটা নিজে বুঝে নাও।

Source

• 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)

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।

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।

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 যথেষ্ট" আবছা থাকবে।

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।

5. Visual explanation

97 (prime) আর 91 (ছদ্মবেশী composite) — দুটোতে trial division পাশাপাশি দেখো:

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।

6. Example input and output

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 লাগে)।

7. Brute force thinking

সবচেয়ে সরল ভাবনা — 2 থেকে n-1 পর্যন্ত প্রতিটা সংখ্যা দেখি, কেউ ভাগ করে কিনা:

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।

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, প্রথম ভাজক পেলেই থামো:

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-এও কাজে লাগবে।

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।

12. Python solution

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!।

14. Output walkthrough

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

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 সব ক্ষেত্রে সঠিক।

15. Time complexity

O(√n) — loop চলে 2 (বা 3) থেকে √n পর্যন্ত, তাই সর্বোচ্চ ≈ √n বার (বিজোড়-only হলে অর্ধেক, তবু O(√n))। বড় prime 10⁹-এও মাত্র ~31623 ধাপ — চোখের নিমেষে। (brute O(n) — বড় prime-এ 10⁹ ধাপ, অসম্ভব।)

16. Space complexity

O(1) — শুধু i আর n; কোনো list বা array নেই, সংখ্যার আকারের সাথে স্মৃতি বাড়ে না।

17. Common mistakes

1. 1-কে prime ভাবা — এক নম্বর ফাঁদ। 1-এর factor মোটে একটা (নিজে), তাই 1 prime নয়। শুরুতে if n < 2: return False চাই।
2. 2-কে বাদ দেওয়া — অনেকে "জোড় সংখ্যা prime নয়" নিয়ম বসিয়ে 2-কেও False করে ফেলে। 2 হলো একমাত্র জোড় prime — আলাদা handle করো।
3. i <= sqrt(n) দিয়ে float-ভুল — math.sqrt float দেয়, বড় n-এ rounding-এ ভাজক ফসকাতে পারে। সবসময় i * i <= n (integer)।
4. range(2, n+1) দিয়ে নিজেকে দিয়ে ভাগ — n নিজে তো নিজেকে ভাগ করবেই (n % n == 0), তাই loop n পর্যন্ত নিলে সব সংখ্যা ভুল করে composite হবে। range(2, n) বা √n পর্যন্ত যাও।
5. negative ভুলে যাওয়া — -7 prime নয়; if n < 2 সেটাও আটকায়।

18. Harder problems that inherit this idea

• 014 — Print All Primes up to N (এই repo) — এই is_prime-কে 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় ডাকা; সরাসরি পরের ধাপ।
• 016 — Prime Factorization (এই repo) — সংখ্যাটাকে prime-দের গুণফলে ভাঙা; ভেতরে এই "ছোট prime দিয়ে ভাগ যায় কিনা" চিন্তা। সম্পর্কিত: Project Euler 3 (https://projecteuler.net/problem=3)।
• LeetCode — Count Primes (https://leetcode.com/problems/count-primes/) — N পর্যন্ত কতগুলো prime; বড় N-এ trial division ধীর হয়, তাই sieve লাগে (015) — এই problem prime check থেকে sieve-এ যাওয়ার সেতু।

19. Pattern learned

Prime check via √n trial division — 2 থেকে √n পর্যন্ত একটাও ভাজক না পেলে prime, প্রথম ভাজকেই composite (early exit)। বড় শিক্ষা: 012-এর √n factor-যুক্তিটাই এখানে "একটা ভাজক খুঁজে পাওয়াই যথেষ্ট" রূপে ফিরেছে; আর 2 আলাদা সামলে শুধু বিজোড় দেখার trick কাজ অর্ধেক করে। এই prime check পরের সব prime-problem-এর ইট।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "is_prime = n < 2 হলে False; 2 আলাদা True; জোড় হলে False; তারপর i*i <= n পর্যন্ত শুধু বিজোড় i দিয়ে ভাগ, একটাও মিললে composite, নাহলে prime। 1 prime নয়, 2 একমাত্র জোড় prime, 91 = 7×13 (চোখে prime মনে হলেও নয়)।"

আগের ধাপ → 012 — Count Factors (যে √n loop থেকে এল)। পরের ধাপ → 014 — Print All Primes up to N (এই check বারবার ডেকে)। তারও পরে → 016 — Prime Factorization।

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

21. JavaScript solution (with test cases)

JS-এও % আছে, কিন্তু integer division নেই — তাই i * i <= n দিয়েই √n সীমা মাপি (Math.sqrt এড়িয়ে)।

// 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 আটকায়।

22. TypeScript solution (with test cases)

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<T>(actual: T, expected: T, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: got ${actual}`);
}

const cases: ReadonlyArray<readonly [number, boolean]> = [
  [2, true], [7, true], [97, true],
  [1, false], [0, false], [-7, false], [4, false], [91, false], [9, false],
];
for (const [n, want] of cases) expect(isPrime(n), want, `n=${n}`);
console.log("সব TS test pass!");

TS টীকা: return type boolean আর [number, boolean] tuple টাইপ দিলে test table-এ ভুল ধরন (যেমন expected-এ string) compile-time-এই ধরা পড়ে — runtime-এ পৌঁছায় না।

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

• Cryptography (RSA): বড় prime খোঁজা/যাচাই করাই public-key encryption-এর ভিত্তি; এখানে আরও দ্রুত probabilistic test (Miller-Rabin) লাগে, কিন্তু ভিত্তি একই প্রশ্ন।
• Hash table sizing: bucket সংখ্যা prime নিলে collision distribution ভালো হয় — তাই অনেক hash implementation prime-আকার বাছে।
• Random/unique ID generation: prime modulus দিয়ে spread ভালো রাখা (যেমন hashing, linear congruential RNG)।
• Input validation / math utility: "এই সংখ্যা কি prime" — calculator, education app, competitive-programming helper-এ নিত্য। মূল pattern — "√n পর্যন্ত একটা ভাজক খুঁজে পাওয়াই যথেষ্ট, early exit" — factorization, divisor-গোনা, sieve সবখানে বড় ছবিতে ফেরে।

---

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