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)

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-এর পছন্দ

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।

ধারণায় ফিরি · সব সমস্যা ও অনুশীলন · মূল উৎস