De ce contează?
Fracția 8/15 nu poate fi simplificată — 8 și 15 nu au niciun divisor comun în afară de 1. Spunem că sunt „prime între ele". Asta nu înseamnă că fiecare e număr prim în sine. Înseamnă că, împreună, nu au niciun „factor comun" care ar permite simplificarea.
Definiție
Două numere a și b sunt prime între ele (sau coprime) dacă CMMDC(a, b) = 1. Nu au niciun factor comun mai mare decât 1.
Exemple:
| a | b | CMMDC | Prime între ele? |
|---|---|---|---|
| 8 | 15 | 1 | ✓ |
| 6 | 10 | 2 | ✗ |
| 7 | 13 | 1 | ✓ (ambele prime) |
| 9 | 16 | 1 | ✓ (niciunul nu e prim) |
Două numere prime distincte sunt întotdeauna prime între ele. Dar pot fi coprime și numere care nu sunt prime individual: 8 (= 2³) și 9 (= 3²) nu au factori comuni, deci sunt coprime — deși niciunul nu este număr prim.
Implementare C++
#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int a, b;
cin >> a >> b;
if (cmmdc(a, b) == 1)
cout << a << " si " << b << " sunt prime intre ele" << endl;
else
cout << a << " si " << b << " nu sunt prime intre ele" << endl;
return 0;
}Exemple: 8 15 → prime între ele; 6 10 → nu sunt prime între ele
De ce contează?
O fracție a/b este ireductibilă exact atunci când a și b sunt prime între ele. Orice simplificare a fracțiilor — în matematică sau în probleme de concurs — se reduce la verificarea dacă CMMDC = 1.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Verificare coprime | O(log(min(a,b))) | O(1) |
Greșeala 1: Confunzi „prime între ele" cu „ambele sunt numere prime". Sunt concepte distincte. 8 și 9 sunt prime între ele, dar niciunul nu este număr prim.
Greșeala 2: Verifici individual dacă fiecare număr e prim pentru a decide dacă sunt coprime. Nu funcționează: 4 și 9 sunt coprime dar niciunul nu e prim; 2 și 4 nu sunt coprime deși 2 e prim.
Greșeala 3: CMMDC(a, a) = a, nu 1. Un număr nu este coprim cu el însuși (cu excepția lui 1).