Problem link ও উৎস
- **Original source:** Classic exercise
- **Platform:** Classic exercise / — (judge-free)
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Easy
- **Pattern:** gcd(a, b) == 1
- **Basic idea inherited from:** 018 — GCD using Euclidean Algorithm
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো ধনাত্মক integer `a` আর `b` দেওয়া আছে। বলতে হবে এরা **coprime** (পরস্পর মৌলিক / relatively prime) কি না। coprime মানে — এদের মধ্যে 1 ছাড়া আর কোনো common factor নেই।
উদাহরণ: 8 আর 15 coprime, কারণ 8 = 2×2×2 আর 15 = 3×5 — কোনো prime মেলে না, তাই একমাত্র common factor 1। আবার 12 আর 18 coprime নয়, কারণ দুজনকেই 6 (এবং 2, 3) ভাগ করে।
মজার ব্যাপার: 8 আর 15 — দুটোর কেউই নিজে prime নয়, তবু এরা coprime! coprime হওয়াটা নিজে prime হওয়ার সাথে এক জিনিস নয়।
### Input ও output {#6-example-input-and-output}
```text
a , b -> coprime? (gcd)
-----------------------------------
8 , 15 -> True (gcd 1)
12 , 18 -> False (gcd 6)
17 , 5 -> True (gcd 1, দুটোই prime)
9 , 28 -> True (gcd 1, কেউই prime নয় তবু coprime)
14 , 21 -> False (gcd 7)
1 , 1 -> True (gcd 1)
1 , 10 -> True (1 সবার সাথে coprime)
6 , 6 -> False (gcd 6, একই সংখ্যা)
```
দুটো জিনিস খেয়াল করো: **1 প্রত্যেকের সাথে coprime** (gcd(1, যেকোনো) = 1)। আর coprime হতে দুজনের কাউকে prime হতে হয় না — 9 আর 28 দুজনেই composite, তবু coprime।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুটো cogwheel (দাঁতওয়ালা চাকা) একসাথে ঘুরছে — একটায় 8টা দাঁত, আরেকটায় 15টা। প্রথম চাকার একটা নির্দিষ্ট দাঁত আবার ঠিক সেই জায়গায় দ্বিতীয় চাকার একই দাঁতের সাথে কখন মিলবে?
8 আর 15 coprime বলে — সব দাঁত একে অপরের সাথে অন্তত একবার মিলবে, তারপর পুরো cycle (8×15 = 120 ধাপ) শেষে আবার শুরুর জায়গায় ফিরবে। দাঁত সমানভাবে "মিশে" যায়, কোনো দাঁত বারবার একই দাঁতের সাথে আটকে থাকে না।
কিন্তু 12 আর 18 হলে (common factor 6) — কিছু দাঁত বারবার একই কয়েকটা দাঁতের সাথেই মেলে, পুরো মিশ্রণ হয় না। সেই "পুরোপুরি মিশে যাওয়া বনাম আটকে থাকা"-র পার্থক্যই coprime বনাম not-coprime।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **018 (GCD using Euclidean Algorithm)**-এর একটা এক-লাইনের প্রয়োগ। gcd function থাকলে coprime check প্রায় কিছুই না — শুধু `gcd(a, b) == 1` লেখা।
তাই এটা আলাদা একটা বড় algorithm নয়, বরং GCD-র একটা গুরুত্বপূর্ণ "use case"। আটকে গেলে 018-এ ফিরে যাও; gcd ঠিক থাকলে এটা আপনাআপনি ঠিক। আর এই problem নিজে এগিয়ে দেয় 022 (Count Coprime Pairs) আর 023 (Euler Phi)-এর দিকে — দুটোতেই "gcd == 1" বারবার লাগবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea একদম সরল, আর সম্পূর্ণভাবে GCD-র উপর:
```text
a আর b coprime <=> gcd(a, b) == 1
```
কেন? gcd হলো দুজনের **সবচেয়ে বড়** common divisor। যদি সেই সবচেয়ে বড়টাই 1 হয়, তার মানে 1-এর বড় কোনো common divisor নেই — অর্থাৎ কোনো common factor নেই (1 ছাড়া)। সেটাই তো coprime-এর সংজ্ঞা।
তাই আলাদা করে কিছু আবিষ্কার করার নেই — gcd বের করো (018-এর Euclid), আর সেটা 1 কি না দেখো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
GCD-সূত্র মাথায় না এলে, সবচেয়ে সরল চিন্তা — 2 থেকে শুরু করে min(a, b) পর্যন্ত প্রতিটা সংখ্যা দিয়ে দেখি, কেউ দুজনকেই ভাগ করে কি না। একটাও পেলে coprime নয়:
```python
def is_coprime_brute(a, b):
a, b = abs(a), abs(b)
for d in range(2, min(a, b) + 1):
if a % d == 0 and b % d == 0:
return False # common factor পাওয়া গেছে
return True # 1 ছাড়া কেউ মেলেনি
```
এটা প্রতিটা সম্ভাব্য common factor (2, 3, 4, ... min) ঘুরে দেখে; একটাও দুজনকে ভাগ করলেই coprime নয়। কেউ না মিললে coprime। সরল, ঠিক উত্তর দেয়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা হলো এই loop `min(a, b) − 1` বার পর্যন্ত ঘোরে। ছোট সংখ্যায় টের পাবে না, কিন্তু a, b দুটোই বড় আর coprime হলে (যেমন দুটো বড় prime ~10⁹) loop প্রায় পুরো min(a, b) বার চলবে — কারণ কোনো common factor কখনো পাবে না, তাই শেষ পর্যন্ত ঘুরবে।
```text
a, b দুটো ~10^9 আর coprime হলে:
brute force : ~10^9 বার loop (ধীর, O(min(a, b)))
gcd দিয়ে : ~30 ধাপের কম (O(log min(a, b)))
```
মূল কথা: প্রতিটা divisor হাতড়ে দেখা অপচয়, যখন gcd একবারেই সবচেয়ে বড় common divisor বলে দেয়। সেটা 1 কি না — এক তুলনায় শেষ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **coprime হওয়া মানে gcd ঠিক 1; তাই প্রতিটা factor খোঁজার দরকার নেই, শুধু gcd 1 কি না দেখলেই হলো।**
GCD আমরা 018-এ Euclid দিয়ে O(log) সময়ে বের করতে শিখেছি। তাই:
```python
def is_coprime(a, b):
return gcd(a, b) == 1
```
ব্যস। gcd সবচেয়ে বড় common divisor; সেটা 1 মানে 1-এর বড় কোনো common divisor নেই — তাই coprime। brute force-এর min(a, b) ধাপ এক লাইনে নেমে এল।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **"কোনো common factor আছে কি না" — এই প্রশ্নটা আসলে "gcd 1 কি না" প্রশ্নেরই অন্য চেহারা।**
মূল মোচড়টা এই উপলব্ধি — সবচেয়ে বড় common divisor যদি 1 হয়, তাহলে স্বয়ংক্রিয়ভাবে 1-এর বড় আর কোনো common divisor নেই (কারণ থাকলে gcd সেটাই হতো, 1 নয়)। তাই সব factor আলাদা করে দেখার দরকারই নেই — gcd একটাই সংখ্যায় পুরো উত্তর ধরে রাখে। এই "একটা সংখ্যা পুরো প্রশ্নের জবাব দেয়" চিন্তাটা মনে রাখো।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে factorization দিয়ে দেখো — common prime আছে কি নেই:
```text
coprime উদাহরণ:
8 = 2 · 2 · 2
15 = 3 · 5
কোনো prime মেলে না -> gcd = 1 -> coprime ✓
not-coprime উদাহরণ:
12 = 2 · 2 · 3
18 = 2 · 3 · 3
2 আর 3 মেলে -> gcd = 2·3 = 6 -> coprime নয় ✗
```
এবার gcd-এর সিদ্ধান্তটা ছবিতে:
```text
gcd(a, b) বের করো:
== 1 -> coprime (1 ছাড়া কোনো common divisor নেই)
> 1 -> coprime নয় (gcd নিজেই একটা common factor)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো is_coprime(8, 15) ধীরে চালাই। আগে gcd(8, 15) বের করি (Euclid), তারপর 1-এর সাথে তুলনা:
| step | a | b | a % b |
| --- | --- | --- | --- |
| 1 | 8 | 15 | 8 |
| 2 | 15 | 8 | 7 |
| 3 | 8 | 7 | 1 |
| 4 | 7 | 1 | 0 → থামো, gcd = 1 |
gcd = 1, তাই `1 == 1` → **True** → coprime। মিলিয়ে দেখো: 8 = 2³, 15 = 3×5 — সত্যিই কোনো prime মেলে না।
তুলনায় is_coprime(12, 18): gcd(12, 18) = 6 (018-এর dry run-এর মতো), আর `6 == 1` মিথ্যা → **False** → coprime নয়।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def gcd(a, b):
"""018-এর Euclid — coprime check-এর ভিত্তি।"""
a, b = abs(a), abs(b)
while b:
a, b = b, a % b
return a
def is_coprime(a, b):
"""a আর b coprime (gcd == 1) হলে True, নাহলে False।"""
return gcd(a, b) == 1
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert is_coprime(8, 15) is True # gcd 1
assert is_coprime(12, 18) is False # gcd 6
assert is_coprime(17, 5) is True # দুটোই prime
assert is_coprime(9, 28) is True # কেউই prime নয়, তবু coprime
assert is_coprime(14, 21) is False # gcd 7
assert is_coprime(1, 1) is True # gcd 1
assert is_coprime(1, 10) is True # 1 সবার সাথে coprime
assert is_coprime(6, 6) is False # gcd 6
assert is_coprime(35, 64) is True # 5·7 আর 2^6 -> coprime
print(is_coprime(8, 15)) # True
print(is_coprime(12, 18)) # False
print(is_coprime(9, 28)) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def gcd(a, b):
a, b = abs(a), abs(b)
while b:
a, b = b, a % b
return a
```
এটা 018-এর Euclid — coprime check-এর পুরো ভিত্তি। বড় জোড়াকে ছোট জোড়ায় নামিয়ে `b = 0` হলে `a`-ই gcd।
```text
def is_coprime(a, b):
return gcd(a, b) == 1
```
এটাই হৃদয়, এক লাইন। `gcd(a, b)` দেয় সবচেয়ে বড় common divisor; সেটা ঠিক 1 হলে `== 1` দেয় True (coprime), নাহলে False। কোনো loop নেই — gcd-ই সব কাজ করে দিয়েছে।
লক্ষ করো assert-গুলোতে `is True` / `is False` ব্যবহার করেছি — কারণ function ঠিক boolean ফেরত দেয় (truthy কিছু নয়), তাই identity check-ও নিরাপদ আর পরিষ্কার।
বাকি `assert` লাইনগুলো নিজেদের চেক করছে; সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
True
False
True
সব test pass!
```
প্রথম তিন লাইন তিনটা `print(is_coprime(...))` থেকে: (8,15) → True (gcd 1), (12,18) → False (gcd 6), (9,28) → True (gcd 1, যদিও দুটোই composite)। তার আগের সব `assert` চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log min(a, b))** — পুরো খরচটাই gcd বের করায় (Euclid, O(log))। তারপর একটাই তুলনা (`== 1`) — constant। তাই 018-এর GCD যত দ্রুত, coprime check-ও ঠিক তত দ্রুত। brute force-এর O(min(a, b))-এর তুলনায় বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — gcd iterative হওয়ায় শুধু গুটিকয় variable লাগে, কোনো বাড়তি list বা array নেই। input ছাড়া আলাদা জায়গা প্রায় শূন্য।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **coprime আর prime গুলিয়ে ফেলা** — coprime হতে দুজনের কাউকে prime হতে হয় না (9 আর 28 coprime, দুটোই composite)। coprime দুটো সংখ্যার *সম্পর্ক*, prime একটা সংখ্যার *গুণ*।
2. **1-কে বাদ দেওয়া** — 1 প্রত্যেকের সাথে coprime (gcd সবসময় 1)। অনেকে ভুলে যায়।
3. **gcd == 0 আর gcd == 1 গুলিয়ে ফেলা** — gcd(0, 0) = 0; এটা coprime নয়। সবসময় ঠিক 1-এর সাথে তুলনা করো।
4. **নিজে নিজে factor খোঁজা** — gcd জানা থাকতে প্রতিটা divisor হাতড়ানো অপচয়; এক লাইনের gcd check-ই যথেষ্ট।
5. **truthy চেক করা** — `if gcd(a, b)` লিখলে সেটা "gcd শূন্য নয়" বোঝায়, "coprime" নয়। সবসময় স্পষ্ট করে `== 1`।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Euler's totient function** (