Level 1 — Divisibility, Prime, GCD, LCM (ভাগের জগৎ)¶

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 শেষ — বিশেষ করে %, // আর 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	divisibility	Classic exercise
012	Count Factors	√n factor pairs	Classic exercise
013	Check Prime	trial division	Classic exercise
014	Print All Primes up to N	repeated prime check	Classic exercise
018	GCD using Euclidean Algorithm	Euclid	CP-Algorithms — https://cp-algorithms.com/algebra/euclid-algorithm.html
020	LCM using GCD	lcm = a*b/gcd	Classic (related: Project Euler 5 — https://projecteuler.net/problem=5)
021	Coprime Check	gcd = 1	Classic exercise

Medium¶

#	Problem	Pattern	Source
015	Sieve of Eratosthenes	sieve	CP-Algorithms — https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html (related: LeetCode Count Primes — https://leetcode.com/problems/count-primes/)
016	Prime Factorization	peeling primes	Classic (related: Project Euler 3 — https://projecteuler.net/problem=3)
017	Smallest Prime Factor	SPF sieve	CP-Algorithms sieve variants
022	Count Coprime Pairs Basic	gcd over pairs	Classic exercise
023	Euler Phi Basic	totient formula	CP-Algorithms — https://cp-algorithms.com/algebra/phi-function.html
024	Number of Divisors	exponent formula	CSES Counting Divisors — https://cses.fi/problemset/task/1713
025	Sum of Divisors	exponent formula	Classic (harder variant: CSES Sum of Divisors — https://cses.fi/problemset/task/1082)

Hard¶

#	Problem	Pattern	Source
019	Extended GCD Intro	back-substitution	CP-Algorithms — https://cp-algorithms.com/algebra/extended-euclid-algorithm.html

পুরো tracker table (status সহ) আছে problems/README.md-তে।

Recommended order¶

011 → 012 — divisibility দিয়ে শুরু, তারপর factor pair আর √n-এর জাদু
013 → 014 — prime check, তারপর সেটা দিয়ে অনেক prime বের করা (আর বুঝবে কেন slow)
015 → 016 → 017 — sieve দিয়ে দ্রুত করা, factorization, SPF — এই তিনটা একসাথে একটা গল্প
018 → 020 → 021 — Euclid GCD, তারপর LCM আর coprime (GCD পরিবার)
022 → 023 — coprime গোনা, তারপর Euler phi (একটা সংখ্যার coprime বন্ধু কয়জন)
024 → 025 — factorization থেকে divisor count/sum formula
019 (Hard) — সবশেষে Extended GCD; এটা Level 2-এর modular inverse-এর সেতু, এখন শুধু পরিচয় হলেই হবে

Common mistakes (সাধারণ ভুল)¶

Loop n পর্যন্ত চালানো — factor খুঁজতে বা prime check করতে range(2, n) লিখলে কাজ করে, কিন্তু n = 10⁹ হলে শেষ হবে না। √n পর্যন্তই যথেষ্ট — i * i <= n লেখো।
Perfect square-এ factor double গোনা — 36-এর factor pair (6, 6); দুবার গুনলে উত্তর 1 বেশি হয়ে যায়। i * i == n হলে একবার গোনো।
1-কে prime ভাবা — 1 prime না, composite-ও না। n < 2 হলে সরাসরি "not prime" ফেরত দাও — এটা সবচেয়ে কমন bug।
Sieve-এ marking শুরু করা 2*i থেকে — i*i থেকে শুরু করলেই হয়; তার আগের multiple গুলো ছোট prime-রা আগেই কেটে দিয়েছে। 2*i থেকে শুরু করলে ভুল না, কিন্তু অযথা slow।
lcm = a * b / gcd লিখে float বানিয়ে ফেলা — Python-এ / দিলে float আসে, বড় সংখ্যায় precision হারায়। সবসময় a * b // gcd (integer division) আর আগে gcd দিয়ে ভাগ: a // gcd(a, b) * b।
Factorization loop-এ একই prime একবারই ভাগ করা — 12 থেকে 2 একবার ভাগ করলে 6 থাকে, ওর ভেতরেও 2 আছে! while n % p == 0 দিয়ে এক prime নিঃশেষে ছাড়াও, তারপর পরের prime-এ যাও।
gcd(a, 0) ভুলে যাওয়া — Euclid-এর base case: gcd(a, 0) = a। এটা ভুললে recursion থামবে না।
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-এ, যেখানে % operator তার আসল রূপ দেখাবে।

Source map¶

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।