134 — Primality Test Advanced

এই note-এ আমরা primality testing-এর গভীরে নামব — Level 1-এর সরল trial division কোথায় থেমে যায়, আর কীভাবে তাকে শান দেওয়া যায়। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — তবে "এই সংখ্যাটা prime কি না" interview-তেও মাঝে মাঝে আসে (যদিও Miller-Rabin-এর গভীরতা নয়)। 013 (trial division primality) ঝালাই থাকলে এটা স্বাভাবিক পরের ধাপ। এটা primality trilogy-র (134 → 135 → 136) প্রথম ধাপ।

Source

• Original source: CP-Algorithms — Primality Tests
• Platform: CP-Algorithms — https://cp-algorithms.com/algebra/primality_tests.html
• Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
• Difficulty: Medium
• Pattern: beyond trial division
• Basic idea inherited from: 013 (Trial Division Primality)

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 যথেষ্ট, কখন আরও ভালো পদ্ধতি লাগে" — এই সিদ্ধান্তটা শেখার দারুণ উদাহরণ।

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 আসে।

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।

4. Real-life analogy

ভাবো তোমাকে একটা সংখ্যক চকলেট ঠিক সমান ভাগে কয়েকজনের মধ্যে বিলি করতে হবে — যদি কোনোভাবেই (1 জন বা সবাইকে একসাথে ছাড়া) সমান ভাগ না হয়, সংখ্যাটা prime।

এখন তুমি কি 2 থেকে n−1 জন পর্যন্ত প্রতিটা দল-আকার চেষ্টা করবে? অপচয়! একটু ভেবে দেখো:

• দল যদি n-এর অর্ধেকের বেশি বড় হয়, তাহলে প্রত্যেকে 1টার কম পাবে — তাই বড় দল দেখার দরকার নেই (√n-এর যুক্তি)।
• দল-আকার জোড় হলে আগেই জানো 2 দিয়ে ভাগ যায় কি না — তাই জোড় দল আলাদা করে দেখার দরকার নেই।
• বেশিরভাগ "সম্ভাব্য prime দল-আকার" 6-এর আশেপাশে একটা প্যাটার্নে পড়ে (6k±1) — বাকিগুলো এমনিতেই 2 বা 3 দিয়ে ভাগ যায়।

এই সব বাদ দিয়ে তুমি অনেক কম দল-আকার চেষ্টা করেই রায় দিতে পারো।

5. Visual explanation

is_prime(37) — 6k±1 trial division-এ:

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-এর মধ্যেই।

6. Example input and output

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-কে ফাঁকি দেয়।

7. Brute force thinking

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

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 বড় হলেই অচল:

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 ভাজক দেখো। ধাপ:

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।

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

12. Python solution

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

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

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)। কোন মাপে কোন পদ্ধতি — সেটা বোঝা জরুরি।

18. Harder problems that inherit this idea

• CSES — Counting Primes / প্রচুর prime query (https://cses.fi/problemset/) — অনেক বড় সংখ্যার primality, যেখানে trial division থেমে যায় আর Miller-Rabin লাগে।
• Codeforces — "is n prime" বড় n-এর constructive problems (https://codeforces.com/problemset) — n বড় হলে deterministic Miller-Rabin।
• 135 (Miller-Rabin Intro) আর 136 (Pollard Rho) — এই repo-রই পরের দুই ধাপ; 134-এর সীমা থেকেই 135-এর প্রয়োজন।

19. Pattern learned

Beyond trial division: √n + 6k±1 — composite-এর ভাজক ≤ √n, আর 2, 3 ছাড়া সব prime 6k±1; তাই √n পর্যন্ত শুধু 6k±1 ভাজক দেখো (O(√n))। বড় শিক্ষা: প্রথমে অপ্রয়োজনীয় কাজ ছাঁটো (√n, জোড়-বাদ), কিন্তু order যখন তাও বড্ড বেশি, তখন একদম ভিন্ন algorithm খোঁজো — এক optimization-এ আটকে থেকো না।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "primality: n<2 না, 2/3 আলাদা, তারপর 6k±1 দিয়ে √n পর্যন্ত ভাগ (O(√n)); n বড় (10¹⁸) হলে এটা অচল — Miller-Rabin (135)।" Signal: "n prime কি না, n মাঝারি" → 6k±1 trial division; "n বিশাল" → পরের ধাপ Miller-Rabin।

পরের ধাপ → 135 — Miller-Rabin Intro (probabilistic ও 64-bit deterministic primality)। ভিত্তি → 013 (Trial Division Primality)।

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

---

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