# Factor, sieve ও GCD — চিত্রে বোঝা

## Factor জোড়া: 36

| ছোট factor | বড় factor | গুণফল |
| --- | --- | --- |
| 1 | 36 | 36 |
| 2 | 18 | 36 |
| 3 | 12 | 36 |
| 4 | 9 | 36 |
| 6 | 6 | 36 |

6-এর পরে একই জোড়া উল্টোভাবে আসে। মাঝের 6 একবার গুনলে মোট 9টি divisor।

## Sieve: 2 থেকে 20-এর সম্পূর্ণ ছোট উদাহরণ

| ধাপ | নতুন করে বাদ পড়ে | বেঁচে থাকা প্রার্থী |
| --- | --- | --- |
| শুরু | 1 prime নয় | 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 |
| p=2, শুরু p²=4 | 4,6,8,10,12,14,16,18,20 | 2,3,5,7,9,11,13,15,17,19 |
| p=3, শুরু p²=9 | 9,15 | 2,3,5,7,11,13,17,19 |

পরের prime 5; `5² > 20`, তাই শেষ। Prime-কে নিজে বাদ দিই না, তার গুণিতক বাদ দিই।

## Euclid: gcd(48,18)

```mermaid
flowchart LR
    A["48, 18"] -->|"48 % 18 = 12"| B["18, 12"]
    B -->|"18 % 12 = 6"| C["12, 6"]
    C -->|"12 % 6 = 0"| D["6, 0"]
    D --> E["GCD = 6"]
```

প্রতিটি ধাপে `gcd(a,b)=gcd(b,a%b)` অপরিবর্তিত থাকে, কিন্তু সংখ্যা ছোট হয়। তাই শেষের nonzero সংখ্যা উত্তর। `lcm(48,18)=(48//6)*18=144`।

**ব্যবহার:** প্রতি 4 ও 6 মিনিটে চলা দুটি কাজ 12 মিনিট পরে আবার একসঙ্গে হবে। কারণ positive common multiple-এর মধ্যে প্রথমটি `lcm(4,6)=12`।

## Prime factor tree ও divisor-এর পছন্দ

```mermaid
flowchart TD
    A["60"] --> B["6"]
    A --> C["10"]
    B --> D["2"]
    B --> E["3"]
    C --> F["2"]
    C --> G["5"]
```

তাই `60=2²×3×5`। Divisor বানাতে 2-এর exponent 0/1/2, 3-এর 0/1, 5-এর 0/1—মোট `3×2×2=12`টি পছন্দ। Divisor-গুলো 1,2,3,4,5,6,10,12,15,20,30,60।

## GCD দিয়ে সমান tile; phi দিয়ে coprime গোনা

21×9 মেঝে একই integer-sized square tile দিয়ে কাটাছেঁড়া ছাড়া ঢাকতে সবচেয়ে বড় tile-এর বাহু `gcd(21,9)=3`। লম্বায় 7টি, চওড়ায় 3টি—মোট 21টি tile।

| 1–12-এর মান | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 12-এর সঙ্গে coprime? | হ্যাঁ | না | না | না | হ্যাঁ | না | হ্যাঁ | না | না | না | হ্যাঁ | না |

বেঁচে থাকা 1,5,7,11; তাই `phi(12)=4`। সূত্রেও `12×(1−1/2)×(1−1/3)=4`।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)