Problem link ও উৎস
- Original source: CP-Algorithms — sieve variants (smallest prime factor / linear sieve) (
)
- Platform: CP-Algorithms
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Medium
- Pattern: SPF sieve
- Basic idea inherited from: 015 (Sieve of Eratosthenes)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যা `N` দেওয়া আছে। 2 থেকে `N` পর্যন্ত প্রতিটা সংখ্যার **smallest prime factor (SPF)** — মানে সবচেয়ে ছোট prime যেটা তাকে ভাগ করে — আগে থেকে বের করে রাখতে হবে।
যেমন: 12-এর SPF 2 (12 = 2×6), 15-এর SPF 3 (15 = 3×5), 7-এর SPF 7 (নিজেই prime), 35-এর SPF 5।
আর এই SPF তালিকা একবার বানালে, যেকোনো `n ≤ N`-কে খুব দ্রুত factorize করা যায় — বারবার `spf[n]` দিয়ে ভাগ করতে করতে নেমে।
### Input ও output {#6-example-input-and-output}
```text
build_spf(N) তৈরির পর:
-----------------------------------------
spf[12] -> 2 (12 = 2×6)
spf[15] -> 3 (15 = 3×5)
spf[7] -> 7 (prime — নিজে)
spf[35] -> 5 (35 = 5×7)
spf[2] -> 2
factorize(n) (spf ব্যবহার করে):
factorize(12) -> {2: 2, 3: 1}
factorize(360) -> {2: 3, 3: 2, 5: 1}
factorize(97) -> {97: 1} (prime, spf[97]=97)
```
মূল কথা: SPF তালিকা একবার বানালে (O(N log log N)), তারপর প্রতিটা `factorize` মাত্র O(log n) — বহু সংখ্যা factorize করতে হলে এটাই সেরা। (একটামাত্র সংখ্যা হলে 016-এর সরাসরি peeling-ই যথেষ্ট, sieve বানানোর দরকার নেই।)
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **বড় ক্লাসে নাম-ডাকা (roll call)**, কিন্তু একটু অন্যভাবে। শিক্ষক prime-দের একে একে ডাকেন, আর প্রতিটা prime তার নামতার ছাত্রদের গায়ে নিজের **স্ট্যাম্প** মারে — কিন্তু নিয়ম হলো, যার গায়ে **আগে স্ট্যাম্প পড়েনি** শুধু তাকেই।
- 2 প্রথমে সব জোড় সংখ্যার (4, 6, 8...) গায়ে "2" স্ট্যাম্প মারে
- 3 এসে যাদের গায়ে এখনো স্ট্যাম্প নেই (9, 15, 21...) তাদের "3" মারে — 6, 12 আগেই 2-এর স্ট্যাম্প পেয়েছে, তাই বাদ
- ফলে প্রতিটা সংখ্যার গায়ে থাকে **সবচেয়ে ছোট prime**-এর স্ট্যাম্প (কারণ ছোট prime আগে ডাক পায়)
12-এর গায়ে "2" (প্রথম স্ট্যাম্প), 15-এর গায়ে "3"। এই স্ট্যাম্প-ই SPF। আর কাউকে factorize করতে হলে — গায়ের স্ট্যাম্প দেখো, ভাগ করো, আবার দেখো — সিঁড়ি বেয়ে নামার মতো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **015 (Sieve of Eratosthenes)** থেকে — কাঠামো প্রায় হুবহু এক, শুধু ঘরে কী লিখছি সেটা বদলেছে।
```
015: is_prime[j] = False -> শুধু "কাটা পড়েছে" (হ্যাঁ/না)
017: spf[j] = i -> "কে প্রথম কাটল" (কোন prime)
```
015-এ আমরা ফেলে দিতাম তথ্য — কে কাটল সেটা ভুলে যেতাম, শুধু "কাটা/অকাটা" রাখতাম। 017-এ সেই হারিয়ে-যাওয়া তথ্যটাই ধরে রাখি — আর সেটুকুই factorization-কে বিদ্যুৎগতি দেয়। সাথে 016-এর peeling idea-ও মিশছে: factorize করার সময় ছোট prime দিয়ে নামি, শুধু এবার "কোন prime" খুঁজতে হয় না — `spf[n]` সরাসরি বলে দেয়। তাই 015 আর 016 দুটোই না বুঝলে এই মিলনটা ধরা কঠিন।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **sieve চালানোর সময় "প্রথম কে কাটল" লিখে রাখা**। 015-এর Sieve-এ আমরা শুধু True/False রাখতাম; এখানে একটা `spf[]` array রাখি, যেখানে প্রতিটা সংখ্যার নিচে লেখা থাকে তাকে প্রথম কোন prime কেটেছে।
```
spf = [0..N] (শুরুতে spf[i] = i ধরা — যেন সবাই নিজে prime)
i = 2 থেকে √N পর্যন্ত:
যদি spf[i] == i (i prime, কেউ কাটেনি):
i*i, i*i+i, ... এর জন্য:
যদি spf[j] == j (j-কে আগে কেউ কাটেনি):
spf[j] = i # i-ই j-এর smallest prime factor
```
তারপর factorize করতে: `while n > 1: p = spf[n]; গোনো; n //= p`। প্রতি ধাপে n অন্তত অর্ধেক হয়, তাই **O(log n)** প্রতি factorization।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
"Brute force" এখানে — প্রতিটা সংখ্যার SPF আলাদা করে খুঁজে বের করা, কোনো precompute ছাড়া:
```python
def smallest_prime_factor(n):
if n % 2 == 0:
return 2
i = 3
while i * i <= n:
if n % i == 0:
return i # প্রথম ভাজকই smallest prime factor
i += 2
return n # কেউ না পেলে n নিজেই prime
def factorize_no_sieve(n):
factors = {}
while n > 1:
p = smallest_prime_factor(n)
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
return factors
```
এটা ঠিক উত্তর দেয় — প্রতিবার √n trial division করে smallest factor খুঁজি (এটা আসলে 016-এর peeling-ই)। একটা-দুটো সংখ্যার জন্য একদম যথেষ্ট।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা তখন, যখন **অনেক** সংখ্যা factorize করতে হয় (যেমন 1 থেকে N সবার):
- প্রতিটা সংখ্যার জন্য আলাদা √n খোঁজা — N সংখ্যার জন্য মোট ≈ O(N√N)। N = 10⁶ হলে ~10⁹ কাজ, ধীর।
```text
1 থেকে N সবাইকে factorize করতে হলে:
per-number trial : O(N√N) ≈ 10^9 -> ধীর
SPF sieve : O(N log log N) বানানো + O(log n) প্রতিটা -> অনেক দ্রুত
```
কোথায় অপচয়? একই কাজ (ছোট factor খোঁজা) বারবার করছি — 12, 24, 36 সবার জন্য আলাদা করে "2 কি ভাগ করে?" আবিষ্কার করছি। SPF sieve একবার সবার smallest factor লিখে রাখে; তারপর প্রতিবার খোঁজা নয়, শুধু **পড়া** (`spf[n]`)। এই "একবার precompute, পরে শুধু lookup" সেই 015-এর কারখানা-দর্শনেরই সম্প্রসারণ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **sieve-এর সময় smallest prime factor লিখে রাখো, পরে শুধু lookup করে নামো:**
```python
def build_spf(N):
spf = list(range(N + 1)) # spf[i] = i (শুরুতে সবাই নিজে)
i = 2
while i * i <= N:
if spf[i] == i: # i prime (কেউ কাটেনি)
for j in range(i * i, N + 1, i):
if spf[j] == j: # j-কে আগে কেউ কাটেনি
spf[j] = i # i-ই j-এর smallest prime factor
i += 1
return spf
def factorize(n, spf):
factors = {}
while n > 1:
p = spf[n] # খুঁজতে হয় না — সরাসরি পড়ি
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
return factors
```
দুটো জরুরি সূক্ষ্মতা: (১) `if spf[j] == j` — শুধু তখনই লিখি যখন j-কে আগে কেউ কাটেনি, যাতে **সবচেয়ে ছোট** prime-ই থেকে যায় (ছোট prime আগে চলে বলে); (২) factorize-এ `p = spf[n]` সরাসরি, কোনো trial division নেই — তাই বিদ্যুৎগতি।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় এক বাক্যে: **015-এর চালুনিতে True/False-এর বদলে "প্রথম কে কাটল" লিখে রাখলে, প্রতিটা সংখ্যার smallest prime factor হাতে থাকে — আর factorization আর খোঁজা নয়, শুধু `spf` ধরে সিঁড়ি বেয়ে নামা।**
এর ভেতরে দুটো "আহা":
- **ছোট prime আগে কাটে বলেই smallest:** sieve-এ i বাড়ে 2, 3, 5... ক্রমে, তাই কোনো সংখ্যার গায়ে প্রথম যে stamp পড়ে সেটাই সবচেয়ে ছোট prime। `if spf[j] == j` শর্তটা এই "প্রথমটাই থাকুক" নিশ্চিত করে।
- **lookup > search:** একবার তথ্য জমিয়ে রাখলে (precompute), পরে প্রতিবার নতুন করে হিসাব না করে শুধু পড়ে নেওয়া — এই tradeoff (একটু বেশি স্মৃতি ও একবারের সময়, বিনিময়ে বহু দ্রুত query) competitive programming-এর কেন্দ্রীয় কৌশল।
### ছবিতে বোঝা {#5-visual-explanation}
2 থেকে 12-এ SPF সাজানো হচ্ছে — ছোট prime আগে স্ট্যাম্প মারে বলে প্রতিটা পায় তার smallest:
```text
শুরুতে spf[i] = i (সবাই নিজে):
i : 2 3 4 5 6 7 8 9 10 11 12
spf : 2 3 4 5 6 7 8 9 10 11 12
i=2 (spf[2]==2, prime): 4,6,8,10,12-এ "2" বসাও (যাদের spf এখনো নিজে):
spf : 2 3 [2] 5 [2] 7 [2] 9 [2] 11 [2]
i=3 (spf[3]==3, prime): 9 থেকে — 9-এ "3"; 12 আগেই 2 পেয়েছে, বাদ:
spf : 2 3 2 5 2 7 2 [3] 2 11 2
i=4: spf[4]==2 ≠ 4 -> 4 prime নয়, skip। i=5: 5*5=25>12 -> শেষ।
চূড়ান্ত SPF: 12->2, 9->3, 15 হলে ->3, prime হলে নিজে
```
এবার SPF দিয়ে `12` factorize — সিঁড়ি বেয়ে নামা:
```text
n=12: spf[12]=2 -> ভাগ -> n=6 (2 গোনো)
n=6 : spf[6]=2 -> ভাগ -> n=3 (2 গোনো)
n=3 : spf[3]=3 -> ভাগ -> n=1 (3 গোনো)
n=1 : থামো -> 12 = 2² × 3
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
দুই ভাগ। প্রথমে `build_spf(12)`-এর কাটাকাটি (`i*i <= 12` মানে i = 2, 3):
| i | spf[i] == i? (prime?) | i² | কোন j-তে spf[j]=i বসে (যদি spf[j]==j) |
| --- | --- | --- | --- |
| 2 | 2==2 ✓ | 4 | 4, 6, 8, 10, 12 → সবার spf = 2 |
| 3 | 3==3 ✓ | 9 | 9 → spf=3; 12 আগেই 2 পেয়েছে (spf[12]≠12), বাদ |
i=4-এ `spf[4]=2 ≠ 4` → skip; i=5-এ `25 > 12` → শেষ। ফলাফল: spf[12]=2, spf[9]=3, prime-রা নিজে।
এবার সেই spf দিয়ে `factorize(12, spf)`:
| n (শুরুতে) | p = spf[n] | ভেতরের while | n হয়ে যায় | factors |
| --- | --- | --- | --- | --- |
| 12 | spf[12]=2 | 12→6 (একবার) | 6 | {2: 1} |
| 6 | spf[6]=2 | 6→3 (একবার) | 3 | {2: 2} |
| 3 | spf[3]=3 | 3→1 (একবার) | 1 | {2: 2, 3: 1} |
n=1, loop থামল। **{2: 2, 3: 1}** = `12 = 2² × 3`। লক্ষ করো — কোনো ভাজক "খুঁজতে" হয়নি, প্রতিবার `spf[n]` সরাসরি বলে দিয়েছে; প্রতি ধাপে n অন্তত অর্ধেক — তাই দ্রুত।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def build_spf(N):
"""2..N প্রতিটা সংখ্যার smallest prime factor — O(N log log N)।"""
spf = list(range(N + 1)) # spf[i] = i (সবাই শুরুতে নিজে)
i = 2
while i * i <= N:
if spf[i] == i: # i prime
for j in range(i * i, N + 1, i):
if spf[j] == j: # আগে কেউ কাটেনি -> এই i-ই smallest
spf[j] = i
i += 1
return spf
def factorize(n, spf):
"""spf array দিয়ে n factorize — প্রতিবার O(log n)।"""
factors = {}
while n > 1:
p = spf[n] # খোঁজা নয়, সরাসরি পড়া
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
return factors
def factorize_check(n):
"""স্বাধীন peeling (016-এর মতো) — যাচাইয়ের জন্য, sieve ছাড়া।"""
factors = {}
p = 2
while p * p <= n:
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
p += 1
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors
# --- ছোট test গুলো (সব pass করা উচিত) ---
N = 1000
spf = build_spf(N)
assert spf[12] == 2
assert spf[15] == 3
assert spf[7] == 7 # prime -> নিজে
assert spf[35] == 5
assert spf[2] == 2
assert spf[97] == 97 # prime
# spf দিয়ে factorize আর স্বাধীন peeling — সব n-এ মেলে কিনা (সোনার যাচাই)
for n in range(2, N + 1):
assert factorize(n, spf) == factorize_check(n)
# prime হলে spf[p] == p, composite হলে spf[c] < c
for n in range(2, 100):
is_prime = factorize_check(n) == {n: 1}
assert (spf[n] == n) == is_prime
print(spf[12]) # 2
print(spf[35]) # 5
print(factorize(360, spf)) # {2: 3, 3: 2, 5: 1}
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
spf = list(range(N + 1))
```
`spf[i] = i` দিয়ে শুরু — মানে "ধরে নিলাম প্রত্যেকে নিজের smallest factor" (prime হলে এটাই সত্যি থাকবে; composite হলে পরে ছোট prime বসবে)। `N + 1` ঘর যাতে index N থাকে।
```
while i * i <= N:
if spf[i] == i:
```
বাইরের loop √N পর্যন্ত (015-এর মতো)। `if spf[i] == i` মানে i-কে কেউ কাটেনি — অর্থাৎ i prime; তবেই তার গুণিতকে stamp মারার মানে আছে।
```
for j in range(i * i, N + 1, i):
if spf[j] == j:
spf[j] = i
```
**এই problem-এর হৃদয়।** i-এর গুণিতক (i² থেকে) ঘুরি; কিন্তু `if spf[j] == j` — শুধু তখনই i বসাই যখন j-কে আগে কেউ কাটেনি। এই শর্তই নিশ্চিত করে **সবচেয়ে ছোট** prime থেকে যায় (বড় prime এসে আর overwrite করতে পারে না)।
```
def factorize(n, spf):
while n > 1:
p = spf[n]
while n % p == 0:
...
n //= p
```
factorize — `p = spf[n]` সরাসরি smallest prime দেয় (খোঁজা নেই), সেটা দিয়ে নিঃশেষে ভাগ ও গোনা, তারপর আবার নতুন `spf[n]`। প্রতি ধাপে n ছোট হয়, n=1-এ থামে।
`for n in range(2, N+1)` loop — spf-ভিত্তিক factorize-কে স্বাধীন peeling-এর সাথে 999টা সংখ্যায় মিলিয়ে যাচাই; দ্বিতীয় loop prime চেনা (spf[n]==n) নিশ্চিত করে। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
2
5
{2: 3, 3: 2, 5: 1}
সব test pass!
```
প্রথম দুই লাইন `spf[12]` → 2 আর `spf[35]` → 5 (smallest prime factor)। তৃতীয় লাইন `factorize(360, spf)` → {2:3, 3:2, 5:1} (= 2³×3²×5, spf ধরে নেমে)। তার আগে সব `assert` — নির্দিষ্ট spf মান, 2..1000 জুড়ে spf-factorize বনাম স্বাধীন peeling-এর মিল, আর prime-চেনা — চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` মানে SPF sieve ও তা দিয়ে factorization সব ক্ষেত্রে সঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
- **`build_spf(N)`:** **O(N log log N)** — 015-এর Sieve-এর মতোই কাটাকাটি, শুধু ঘরে i লিখছি।
- **প্রতিটা `factorize(n, spf)`:** **O(log n)** — প্রতি ধাপে n অন্তত অর্ধেক হয় (smallest prime ≥ 2 দিয়ে ভাগ), তাই বড়জোর log₂ n ধাপ। কোনো trial division নেই।
মানে একবার O(N log log N) খরচ করে তালিকা বানালে, এরপর প্রতিটা query প্রায় বিনামূল্যে — বহু factorization-এ বিশাল সাশ্রয়।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(N)** — `spf` array-তে N+1 ঘর (প্রতিটা ঘরে একটা integer, 015-এর boolean-এর চেয়ে সামান্য বেশি)। এটাই precompute-এর দাম: একটু বেশি স্মৃতি ও একবারের সময়, বিনিময়ে O(log n) factorization — classic time/space tradeoff। বিশাল N-এ স্মৃতি সীমাবদ্ধতা হতে পারে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`if spf[j] == j` শর্ত ভুলে যাওয়া** — এক নম্বর ফাঁদ। শর্ত ছাড়া বড় prime এসে ছোট prime-এর stamp overwrite করতে পারে, তখন `spf` আর "smallest" থাকে না। শুধু প্রথমবার (যখন `spf[j]==j`) লেখা জরুরি।
2. **`spf[i] = list(range(N+1))` ভুল init** — শুরুতে `spf[i] = i` হওয়া চাই (`list(range(N+1))`), যাতে prime-রা স্বাভাবিকভাবে নিজেকে ধরে রাখে; 0/False দিয়ে শুরু করলে prime চেনা ভেঙে যায়।
3. **একটা মাত্র সংখ্যার জন্য sieve বানানো** — শুধু একটা n factorize করতে হলে SPF sieve অপচয় (O(N) স্মৃতি+সময়); তখন 016-এর সরাসরি O(√n) peeling-ই ভালো। SPF-এর লাভ **বহু** query-তে।
4. **factorize-এ ভেতরের while বাদ** — `while n % p == 0` ছাড়া একই prime-এর একাধিক power (যেমন 2³) ঠিকমতো গোনা হবে না; আর n-ও কমবে না।
5. **`i*i` / √N সীমা ভুলে N পর্যন্ত চালানো** — কাজ করে কিন্তু অপচয়; 015-এর মতোই √N যথেষ্ট।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **024 — Number of Divisors** / **025 — Sum of Divisors** (এই repo) — বহু সংখ্যার divisor count/sum দরকার হলে SPF দিয়ে দ্রুত factorize করে exponent থেকে formula।
- **023 — Euler Phi** (এই repo) — একই — SPF দিয়ে দ্রুত factorization করে `∏(1 - 1/p)` প্রয়োগ; বিশেষত অনেক n-এর জন্য phi লাগলে।
- **CP-Algorithms — Linear Sieve** (