# Level 1 — Divisibility, Prime, GCD, LCM (ভাগের জগৎ) [ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md) > Level 0-তে আমরা সংখ্যাকে digit-এ ভেঙেছি। এবার ভাঙব অন্যভাবে — **গুণনীয়ক (factor) দিয়ে**। কোন সংখ্যা কাকে ভাগ করে, prime কারা, দুটো সংখ্যার ভেতরের "common ভাগ" (GCD) কীভাবে বের হয় — এই level টা number theory-র আসল দরজা। ## এই level এ কী শিখবে? একটা সংখ্যাকে এখন থেকে দেখবে তার factor-দের দিয়ে। 12 মানে শুধু "বারো" না — 12 মানে `2 × 2 × 3`, মানে `1, 2, 3, 4, 6, 12` এই ছয়জনের পরিবার। এই চোখটা তৈরি হলে divisor count, GCD, LCM — সব একই গল্পের অংশ হয়ে যায়। মূল idea গুলো: - **Divisibility** — `a % b == 0` মানে b, a-কে নিঃশেষে ভাগ করে - **Factor pair** — divisor রা জোড়ায় আসে, তাই √n পর্যন্ত খুঁজলেই সব পাওয়া যায় - **Prime check** — trial division, আর কেন √n পর্যন্তই যথেষ্ট - **Sieve of Eratosthenes** — অনেকগুলো prime একসাথে বের করার কারখানা - **Prime factorization** — সংখ্যার "DNA" বের করা, আর SPF sieve দিয়ে দ্রুত করা - **Euclid-এর GCD** — `gcd(a, b) = gcd(b, a % b)`, পৃথিবীর প্রাচীনতম algorithm-গুলোর একটা - **LCM, coprime, Euler phi** — GCD-র আত্মীয়স্বজন - **Divisor count/sum formula** — factorization থেকে `(e1+1)(e2+1)...` জাদু ## কেন এই level দরকার? **Competitive programming (CP) এ:** Codeforces আর CSES-এর number theory problem-এর মেরুদণ্ড এটাই। Sieve precompute করে query-র উত্তর দেওয়া, GCD দিয়ে fraction simplify করা, factorization দিয়ে divisor count — এগুলো Div 2 B/C level-এ নিয়মিত আসে। CSES-এর Counting Divisors, Sum of Divisors সরাসরি এই level-এর জিনিস। **Interview এ:** Count Primes, GCD of Strings, Ugly Number — এগুলো common interview pattern। Interviewer প্রায়ই দেখতে চায় তুমি `O(n)` থেকে `O(√n)` এ নামতে পারো কি না — factor pair-এর idea টাই সেই নামার সিঁড়ি। **পরের level গুলোতে:** Level 2-এর modular inverse-এ coprime লাগবে, nCr mod p-তে factorization-এর চিন্তা লাগবে। আর sieve-এর "একবার precompute, বারবার ব্যবহার" pattern-টা পুরো DSA জুড়ে ফিরে ফিরে আসবে। ## Prerequisites - [Level 0: Absolute Basics](../00-absolute-basics/README.md) শেষ — বিশেষ করে `%`, `//` আর `while` loop-এ পুরো স্বাচ্ছন্দ্য - Python-এ list বানানো আর index দিয়ে access করা (`primes[i] = False` ধাঁচের কাজ) - `for i in range(...)` দিয়ে নির্দিষ্ট সীমায় loop চালানো ## Learning goals (checklist) এই level শেষে নিজেকে জিজ্ঞেস করো: - [ ] `a % b == 0` দেখলেই বুঝি "b divides a", আর divisibility rules (2, 3, 5, 9, 10) ব্যাখ্যা করতে পারি - [ ] কেন √n পর্যন্ত খুঁজলেই সব factor পাওয়া যায় — ছবি এঁকে বোঝাতে পারি - [ ] Trial division দিয়ে prime check O(√n)-এ লিখতে পারি, edge case (n=1, n=2) সহ - [ ] Sieve of Eratosthenes-এর crossing-out ছবিটা মাথায় চালাতে পারি, আর code করতে পারি - [ ] যেকোনো সংখ্যার prime factorization বের করতে পারি (ছোট prime দিয়ে খোসা ছাড়িয়ে) - [ ] SPF sieve কী আর কেন factorization দ্রুত করে — বলতে পারি - [ ] Euclid-এর GCD হাতে dry run করতে পারি, আর কেন কাজ করে তার intuition আছে - [ ] `lcm = a * b // gcd(a, b)` — কেন আগে gcd দিয়ে ভাগ, বুঝি - [ ] Coprime মানে কী, আর Euler phi(n) formula দিয়ে বের করতে পারি - [ ] Factorization থেকে divisor count `(e1+1)(e2+1)...` — formula-টা কোথা থেকে এলো জানি ## Problem list মোট 15টা problem — 7টা Easy, 7টা Medium, 1টা Hard। Easy গুলো দিয়ে হাত গরম করো, Medium-এ আসল শেখা, Hard-টা (Extended GCD) এখন intro হিসেবে নিলেই চলবে। ### Easy | # | Problem | Pattern | Source | | --- | --- | --- | --- | | 011 | [Divisibility Rules](problems/011-divisibility-rules.md) | divisibility | Classic exercise | | 012 | [Count Factors](problems/012-count-factors.md) | √n factor pairs | Classic exercise | | 013 | [Check Prime](problems/013-check-prime.md) | trial division | Classic exercise | | 014 | [Print All Primes up to N](problems/014-print-all-primes.md) | repeated prime check | Classic exercise | | 018 | [GCD using Euclidean Algorithm](problems/018-gcd-euclidean.md) | Euclid | CP-Algorithms — | | 020 | [LCM using GCD](problems/020-lcm-using-gcd.md) | lcm = a*b/gcd | Classic (related: Project Euler 5 — ) | | 021 | [Coprime Check](problems/021-coprime-check.md) | gcd = 1 | Classic exercise | ### Medium | # | Problem | Pattern | Source | | --- | --- | --- | --- | | 015 | [Sieve of Eratosthenes](problems/015-sieve-of-eratosthenes.md) | sieve | CP-Algorithms — (related: LeetCode Count Primes — ) | | 016 | [Prime Factorization](problems/016-prime-factorization.md) | peeling primes | Classic (related: Project Euler 3 — ) | | 017 | [Smallest Prime Factor](problems/017-smallest-prime-factor.md) | SPF sieve | CP-Algorithms sieve variants | | 022 | [Count Coprime Pairs Basic](problems/022-count-coprime-pairs.md) | gcd over pairs | Classic exercise | | 023 | [Euler Phi Basic](problems/023-euler-phi-basic.md) | totient formula | CP-Algorithms — | | 024 | [Number of Divisors](problems/024-number-of-divisors.md) | exponent formula | CSES Counting Divisors — | | 025 | [Sum of Divisors](problems/025-sum-of-divisors.md) | exponent formula | Classic (harder variant: CSES Sum of Divisors — ) | ### Hard | # | Problem | Pattern | Source | | --- | --- | --- | --- | | 019 | [Extended GCD Intro](problems/019-extended-gcd-intro.md) | back-substitution | CP-Algorithms — | পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে। ## Recommended order 1. **011 → 012** — divisibility দিয়ে শুরু, তারপর factor pair আর √n-এর জাদু 2. **013 → 014** — prime check, তারপর সেটা দিয়ে অনেক prime বের করা (আর বুঝবে কেন slow) 3. **015 → 016 → 017** — sieve দিয়ে দ্রুত করা, factorization, SPF — এই তিনটা একসাথে একটা গল্প 4. **018 → 020 → 021** — Euclid GCD, তারপর LCM আর coprime (GCD পরিবার) 5. **022 → 023** — coprime গোনা, তারপর Euler phi (একটা সংখ্যার coprime বন্ধু কয়জন) 6. **024 → 025** — factorization থেকে divisor count/sum formula 7. **019 (Hard)** — সবশেষে Extended GCD; এটা Level 2-এর modular inverse-এর সেতু, এখন শুধু পরিচয় হলেই হবে ## Common mistakes (সাধারণ ভুল) 1. **Loop `n` পর্যন্ত চালানো** — factor খুঁজতে বা prime check করতে `range(2, n)` লিখলে কাজ করে, কিন্তু n = 10⁹ হলে শেষ হবে না। √n পর্যন্তই যথেষ্ট — `i * i <= n` লেখো। 2. **Perfect square-এ factor double গোনা** — 36-এর factor pair (6, 6); দুবার গুনলে উত্তর 1 বেশি হয়ে যায়। `i * i == n` হলে একবার গোনো। 3. **1-কে prime ভাবা** — 1 prime না, composite-ও না। `n < 2` হলে সরাসরি "not prime" ফেরত দাও — এটা সবচেয়ে কমন bug। 4. **Sieve-এ marking শুরু করা `2*i` থেকে** — `i*i` থেকে শুরু করলেই হয়; তার আগের multiple গুলো ছোট prime-রা আগেই কেটে দিয়েছে। `2*i` থেকে শুরু করলে ভুল না, কিন্তু অযথা slow। 5. **`lcm = a * b / gcd` লিখে float বানিয়ে ফেলা** — Python-এ `/` দিলে float আসে, বড় সংখ্যায় precision হারায়। সবসময় `a * b // gcd` (integer division) আর আগে gcd দিয়ে ভাগ: `a // gcd(a, b) * b`। 6. **Factorization loop-এ একই prime একবারই ভাগ করা** — 12 থেকে 2 একবার ভাগ করলে 6 থাকে, ওর ভেতরেও 2 আছে! `while n % p == 0` দিয়ে এক prime নিঃশেষে ছাড়াও, তারপর পরের prime-এ যাও। 7. **`gcd(a, 0)` ভুলে যাওয়া** — Euclid-এর base case: `gcd(a, 0) = a`। এটা ভুললে recursion থামবে না। 8. **Euler phi formula-তে float division** — `phi = phi * (p - 1) / p` লিখলে float; সঠিক ক্রম: আগে `phi //= p`, তারপর `phi *= (p - 1)`। ## পরের level এ যাওয়ার আগে checklist - [ ] 15টা problem-এর অন্তত 12টা নিজে solve করেছি (Extended GCD-তে আটকালে সমস্যা নেই — Level 2-তে ফিরবে) - [ ] Sieve-এর crossing-out ছবি কাউকে খাতায় এঁকে বোঝাতে পারি - [ ] `gcd(48, 18)` হাতে dry run করে 6 বের করতে পারি, প্রতি step লিখে - [ ] 360-এর prime factorization (2³ × 3² × 5) আর divisor count (4×3×2 = 24) হাতে বের করেছি - [ ] কেন √n পর্যন্ত খোঁজা যথেষ্ট — এক লাইনে উত্তর দিতে পারি ("factor রা জোড়ায় আসে, জোড়ার একজন সবসময় √n-এর এপারে") - [ ] LCM-এ overflow-safe order (`a // g * b`) কেন দরকার, জানি সব টিক দিতে পারলে — চলো [Level 2: Modular Arithmetic](../02-modular-arithmetic/README.md)-এ, যেখানে `%` operator তার আসল রূপ দেখাবে। ## Source map এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।