Concept Notes — Divisibility, Prime, GCD, LCM¶
Level 0-এর মতোই নিয়ম: প্রতিটা snippet-এর mini dry run খাতায় নিজে হাতে করো। এই level-এ ছবিগুলো আরও জরুরি — sieve-এর grid, GCD-র সিঁড়ি — এগুলো একবার চোখে দেখলে আর ভোলা যায় না।
1. Divisor মানে ভাগ মিলে যাওয়া¶
b যদি a-কে নিঃশেষে ভাগ করে — মানে remainder 0 — তাহলে বলি b হলো a-এর divisor (বা factor)। Code-এ এক লাইন:
Mini dry run: 12 % 4 — 12 = 4×3 + 0, remainder 0 → divisor। আবার 12 % 5 — 12 = 5×2 + 2, remainder 2 → divisor না।
Analogy: 12টা লাড্ডু 4 জনকে দিলে কারো মন খারাপ হয় না — প্রত্যেকে 3টা করে, হাতে কিছু থাকে না। 5 জনকে দিলে 2টা লাড্ডু নিয়ে ঝগড়া — remainder-ই সেই ঝগড়ার লাড্ডু। Divisibility মানে ঝগড়াহীন ভাগ।
কিছু চেনা divisibility rule (কেন কাজ করে, Level 2-তে mod দিয়ে প্রমাণ দেখব):
2 -> last digit even 3 -> digit sum 3 দিয়ে ভাগ যায়
5 -> last digit 0 বা 5 9 -> digit sum 9 দিয়ে ভাগ যায় (digital root!)
10 -> last digit 0
2. Factor pair — কেন √n পর্যন্ত খুঁজলেই হয়¶
36-এর সব divisor লিখে একটা মজার জিনিস দেখো:
1 × 36 2 × 18 3 × 12 4 × 9 6 × 6 <- ঠিক মাঝখানে, √36 = 6
36 × 1 18 × 2 12 × 3 9 × 4 এরপর জোড়াগুলোই উল্টে আসে!
Divisor রা জোড়ায় আসে: d যদি divisor হয়, n // d-ও divisor। আর প্রতিটা জোড়ার ছোট জনটা সবসময় √n-এর এপারে থাকে (দুজনেই √n-এর চেয়ে বড় হলে গুণফল n ছাড়িয়ে যেত!)। তাই √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ তুলে নিলেই সব divisor পাওয়া যায়।
def count_factors(n):
count = 0
i = 1
while i * i <= n:
if n % i == 0:
count += 2 # i আর n//i — জোড়া
if i * i == n:
count -= 1 # perfect square: 6×6 একই জন, একবার গোনো
i += 1
return count
Mini dry run (n = 36): i = 1 → জোড়া (1,36), count=2। i=2 → (2,18), count=4। i=3 → (3,12), count=6। i=4 → (4,9), count=8। i=5 → 36%5≠0। i=6 → 6×6=36, count=10, কিন্তু perfect square তাই −1 → 9। মিলিয়ে দেখো: 1,2,3,4,6,9,12,18,36 — ঠিক 9টা।
এটাই এই level-এর সবচেয়ে বড় শিক্ষা: O(n) loop-কে O(√n) এ নামানো। n = 10¹² হলে n-loop অসম্ভব, কিন্তু √n = 10⁶ — এক লহমায় শেষ।
3. Prime check — trial division¶
Prime মানে যার ঠিক দুটো divisor: 1 আর সে নিজে। (তাই 1 prime না — তার divisor মোটে একটা!) Check করার সরল উপায়: 2 থেকে √n পর্যন্ত কেউ ভাগ করে কি না দেখো —
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False # ভাগ মিলে গেছে -> composite
i += 1
return True
Mini dry run (n = 91): i=2 → 91 odd। i=3 → digit sum 10, ভাগ যায় না। i=4 → না। i=5 → last digit 1, না। i=6 → না। i=7 → 91 = 7×13 → False! 91 দেখতে prime-এর মতো, কিন্তু না — এজন্যই check লাগে। আর n = 97 হলে i = 2..9 কেউ ভাগ করে না, i=10-এ 10×10 > 97 → True।
কেন √n যথেষ্ট? Section 2-এর সেই জোড়ার যুক্তি: n-এর কোনো divisor থাকলে তার জোড়ার একজন √n-এর এপারে অবশ্যই আছে।
4. Sieve of Eratosthenes — multiples কেটে ফেলা¶
এক-একটা সংখ্যা আলাদা করে prime check করলে n পর্যন্ত সব prime বের করতে অনেক সময় লাগে। প্রাচীন গ্রিক Eratosthenes-এর কৌশল উল্টো: prime খুঁজো না, composite-দের কেটে ফেলো — যারা বেঁচে থাকবে তারাই prime।
2 থেকে 30-এর grid-এ খেলাটা দেখো:
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
ধাপ 1: 2 বাঁচল, 2-এর multiple সব কাটো (4,6,8,...):
2 3 x 5 x 7 x 9 x
11 x 13 x 15 x 17 x 19 x
21 x 23 x 25 x 27 x 29 x
ধাপ 2: 3 বাঁচল, 3-এর multiple কাটো (9 থেকে শুরু — 6 আগেই কাটা):
2 3 x 5 x 7 x x x
11 x 13 x x x 17 x 19 x
x x 23 x 25 x x x 29 x
ধাপ 3: 5 বাঁচল, 25 কাটো। 7-এ গিয়ে 7×7=49 > 30 — খেলা শেষ!
বেঁচে রইল: 2 3 5 7 11 13 17 19 23 29 -> এরাই prime
Code:
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
i = 2
while i * i <= n:
if is_prime[i]: # i বেঁচে আছে মানে prime
for j in range(i * i, n + 1, i):
is_prime[j] = False # i-এর multiple কাটো
i += 1
return [x for x in range(n + 1) if is_prime[x]]
Mini dry run (n = 20): i=2 → কাটা পড়ে 4,6,8,...,20। i=3 → কাটা পড়ে 9,15 (12,18 আগেই কাটা, তবু আবার False করলে ক্ষতি নেই)। i=4 → is_prime[4] False, skip। i=5 → 5×5=25 > 20, থামো। বেঁচে: 2,3,5,7,11,13,17,19।
দুটো সূক্ষ্ম জিনিস: (1) marking শুরু i * i থেকে — কারণ i-এর ছোট multiple-রা (2i, 3i, ...) আরও ছোট prime-এর হাতে আগেই কাটা পড়েছে; (2) total কাজ n/2 + n/3 + n/5 + ... ≈ O(n log log n) — প্রায় linear, আশ্চর্য দ্রুত। Sieve হলো "একবার কারখানা বানাও, তারপর হাজারটা query free" — এই precompute pattern পুরো CP জুড়ে চলবে।
5. Prime factorization — ছোট prime দিয়ে খোসা ছাড়ানো¶
প্রতিটা সংখ্যার একটা unique "DNA" আছে — prime-দের গুণফল হিসেবে লেখা রূপ। যেমন 360 = 2³ × 3² × 5। বের করার কৌশল: পেঁয়াজের খোসার মতো, সবচেয়ে ছোট prime দিয়ে যতবার পারো ভাগ করো, তারপর পরেরটা।
def factorize(n):
factors = {}
p = 2
while p * p <= n:
while n % p == 0: # এক prime নিঃশেষে ছাড়াও
factors[p] = factors.get(p, 0) + 1
n //= p
p += 1
if n > 1: # যা বাকি, সে নিজেই একটা বড় prime
factors[n] = factors.get(n, 0) + 1
return factors
Mini dry run (n = 360):
| p | ভাগ চলে? | n হয়ে যায় | factors |
|---|---|---|---|
| 2 | 360→180→90→45 | 45 | {2: 3} |
| 3 | 45→15→5 | 5 | {2: 3, 3: 2} |
| 4 | 5 % 4 ≠ 0 | 5 | — |
| 5 | 5×5 > 5, loop শেষ | — | — |
| শেষে | n = 5 > 1 | — | {2: 3, 3: 2, 5: 1} |
দেখো — p prime কি না check করারও দরকার পড়েনি! কারণ p = 4-এ পৌঁছানোর আগে 2 সব নিঃশেষ করে গেছে; composite-এর পালা কখনো আসেই না। আর শেষের if n > 1 — এটাই সবচেয়ে ভোলা অংশ: n = 2 × 7919 হলে loop-এ শুধু 2 ধরা পড়বে, 7919 (বড় prime) পড়ে থাকবে।
SPF (smallest prime factor) sieve: অনেকগুলো সংখ্যা factorize করতে হলে sieve চালানোর সময় প্রতিটা ঘরে লিখে রাখো "তোমাকে প্রথম কে কাটল" — সেটাই তার smallest prime factor। পরে যেকোনো n-কে factorize করতে শুধু spf[n] দিয়ে ভাগ করতে করতে নামো — প্রতি ধাপে অন্তত অর্ধেক হয়, তাই O(log n) প্রতি query! খোঁজাখুঁজি নেই, সিঁড়ি ready।
spf = list(range(n + 1)) # শুরুতে সবাই নিজের spf
for i in range(2, int(n**0.5) + 1):
if spf[i] == i: # i prime
for j in range(i * i, n + 1, i):
if spf[j] == j: # আগে কেউ কাটেনি
spf[j] = i
6. Euclid-এর GCD — gcd(a, b) = gcd(b, a % b)¶
GCD (greatest common divisor) = দুটো সংখ্যাকেই ভাগ করে এমন সবচেয়ে বড় সংখ্যা। Euclid-এর ২৩০০ বছরের পুরোনো আবিষ্কার: gcd(a, b) = gcd(b, a % b) — বড় জোড়াকে ছোট জোড়ায় নামাতে থাকো।
Intuition-টা tile দিয়ে ভাবো: 48 × 18 মেঝেতে সবচেয়ে বড় square tile বসাতে চাও যাতে কাটাকাটি না লাগে। 18 × 18 tile বসালে 48 = 18+18+12 — শেষে 12 × 18 ফালি বাকি। এখন সমস্যা ছোট হয়ে গেল: 18 × 12 ফালিতে একই প্রশ্ন! আবার: 12 × 12 বসাও, বাকি 12 × 6। আবার: 6 × 6 বসাও — মিলে গেল, কিছু বাকি নেই। উত্তর: 6।
48 × 18 মেঝে:
+------------------+------------------+------------+
| | | |
| 18 × 18 | 18 × 18 | 18 × 12 | <- বাকি ফালি
| | | | = নতুন সমস্যা
+------------------+------------------+------------+
48 % 18 = 12 -> এবার 18 × 12 নিয়ে একই খেলা -> 12 % 18...
ধাপে ধাপে: (48,18) -> (18,12) -> (12,6) -> (6,0) -> উত্তর 6
কেন কাজ করে? যে সংখ্যা a আর b দুটোকেই ভাগ করে, সে a − b-কেও করে (আর তাই a % b-কেও) — মানে (a, b) আর (b, a%b)-এর common divisor-এর তালিকা হুবহু একই। তালিকা একই হলে তার সবচেয়ে বড়টাও একই।
Mini dry run (gcd(48, 18)):
| step | a | b | a % b |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| 4 | 6 | 0 | b=0, থামো |
উত্তর 6 — tile-এর গল্পের সাথে হুবহু মিলল। প্রতি দুই ধাপে সংখ্যা অন্তত অর্ধেক হয়, তাই complexity O(log min(a, b)) — 10¹⁸ size-এর সংখ্যাতেও ৯০-এর কম ধাপ!
Extended GCD-র এক ঝলক: Euclid-এর ধাপগুলো উল্টোদিকে হাঁটলে (back-substitution) এমন x, y পাওয়া যায় যাতে a·x + b·y = gcd(a, b)। যেমন 48·(−1) + 18·3 = 6। এখন শুধু এটুকু জানো যে এটা সম্ভব — Level 2-তে modular inverse বের করতে এই কৌশলই কাজে লাগবে।
7. LCM আর coprime — GCD-র দুই আত্মীয়¶
LCM (least common multiple) = দুটো সংখ্যারই multiple এমন সবচেয়ে ছোট সংখ্যা। সূত্র: gcd × lcm = a × b। কেন? Factorization দিয়ে ভাবো — gcd নেয় প্রতিটা prime-এর min power, lcm নেয় max power; আর min + max = দুটোর যোগফল, তাই গুণফল মিলে যায়।
Mini dry run (lcm(12, 18)): gcd(12, 18) = 6 → 12 // 6 = 2 → 2 × 18 = 36। Check: 36 = 12×3 = 18×2 — দুজনেরই multiple, আর এর ছোট কেউ নেই।
Coprime মানে gcd(a, b) = 1 — দুজনের মাঝে কোনো common factor নেই (1 ছাড়া)। যেমন 8 আর 15: 8 = 2³, 15 = 3×5 — কোনো prime মেলে না। মজার ব্যাপার, 8 আর 15 কেউই নিজে prime না, তবু coprime! Coprime-এর ধারণা Level 2-তে modular inverse-এর শর্ত হয়ে ফিরবে — inverse আছে কি না, gcd = 1 দিয়েই নির্ধারিত হয়।
8. Euler phi — n-এর coprime বন্ধু কয়জন?¶
φ(n) = 1 থেকে n-এর মধ্যে কয়টা সংখ্যা n-এর সাথে coprime। যেমন φ(12): তালিকা 1,2,...,12-এর মধ্যে 12-এর সাথে gcd 1 হয় শুধু 1, 5, 7, 11 — তাই φ(12) = 4।
হাতে গোনা ছাড়া formula আছে, factorization থেকে: n-এর প্রতিটা distinct prime p-এর জন্য n-কে (1 − 1/p) গুণ করো —
Intuition: 1..12-এর মধ্যে অর্ধেক 2-এর ভাগে কাটা পড়ে (×1/2 টিকে থাকে), টিকে থাকাদের এক-তৃতীয়াংশ 3-এর ভাগে কাটা পড়ে (×2/3 টিকে থাকে) — sieve-এর crossing-out-এরই ভগ্নাংশ-রূপ!
def phi(n):
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p # result × (1 - 1/p), integer-এ
p += 1
if n > 1:
result -= result // n
return result
Mini dry run (n = 12): p=2 ভাগ যায় → n হয়ে যায় 3, result = 12 − 12//2 = 6। p=3: 3×3 > 3, loop শেষ; n = 3 > 1 → result = 6 − 6//3 = 4। φ(12) = 4 — হাতে গোনার সাথে মিলল। (লক্ষ করো result -= result // p — float এড়ানোর কৌশল।) φ পরে Fermat/Euler theorem-এ (Level 2) প্রধান চরিত্র।
9. Divisor count আর sum — exponent থেকে formula¶
Factorization জানা থাকলে divisor গুনতে আর loop লাগে না। n = p1^e1 × p2^e2 × ... হলে —
Divisor count = (e1+1) × (e2+1) × ...
কেন? একটা divisor বানাতে প্রতিটা prime থেকে "কয়টা নেবে" বেছে নিতে হয়: p1 থেকে 0 থেকে e1 টা — মোট (e1+1) রকম choice। প্রতিটা prime-এর choice independent, তাই গুণ। (এটা আসলে Level 3-এর multiplication principle-এর আগাম দর্শন!)
360 = 2³ × 3² × 5¹
2-এর power বাছো: 2⁰,2¹,2²,2³ -> 4 রকম
3-এর power বাছো: 3⁰,3¹,3² -> 3 রকম
5-এর power বাছো: 5⁰,5¹ -> 2 রকম
মোট divisor = 4 × 3 × 2 = 24
Mini dry run: 36 = 2² × 3² → (2+1)(2+1) = 9 — section 2-এর হাতে-গোনা 9-এর সাথে হুবহু মিলে গেল!
Divisor sum-ও একই যুক্তি, শুধু "কয় রকম" এর জায়গায় "সবগুলো যোগ করলে কত":
sum = (p1⁰ + p1¹ + ... + p1^e1) × (p2⁰ + ... + p2^e2) × ...
36 = 2² × 3²:
sum = (1 + 2 + 4) × (1 + 3 + 9) = 7 × 13 = 91
check: 1+2+3+4+6+9+12+18+36 = 91 ✓
def divisor_count_and_sum(n):
count, total = 1, 1
p = 2
while p * p <= n:
if n % p == 0:
e, power_sum, pw = 0, 1, 1
while n % p == 0:
n //= p
e += 1
pw *= p
power_sum += pw # 1 + p + p² + ...
count *= (e + 1)
total *= power_sum
p += 1
if n > 1:
count *= 2
total *= (1 + n)
return count, total
Mini dry run (n = 12): p=2 → e=2, power_sum = 1+2+4 = 7 → count=3, total=7। p=3-এ পৌঁছানোর আগে n = 3, loop শেষ → n>1: count = 3×2 = 6, total = 7×4 = 28। Check: 12-এর divisor 1,2,3,4,6,12 — সংখ্যায় 6, যোগে 28 ✓।
এক নজরে (cheat sheet)¶
a % b == 0 -> b divides a
i*i <= n loop -> O(√n): factor, prime check
sieve -> multiples কেটে ফেলো, O(n log log n)
factorize -> ছোট prime দিয়ে খোসা ছাড়াও; শেষে n>1 হলে সে-ও prime
spf[n] দিয়ে নামো -> O(log n) factorization (precompute-এর পরে)
gcd(a,b)=gcd(b,a%b) -> Euclid, O(log) ধাপ; gcd(a,0)=a
lcm = a//g * b -> আগে ভাগ, পরে গুণ
coprime -> gcd == 1
φ(n) = n·∏(1-1/p) -> coprime বন্ধু গোনা
d(n) = ∏(eᵢ+1) -> divisor count, exponent থেকে
পরের ধাপ: problems/-এর 15টা problem। তারপর Level 2-তে — যেখানে দেখব % শুধু remainder বের করার tool না, একটা আস্ত গণিতের জগৎ।