Bun, hai să vorbim despre trei concepte matematice fundamentale în programare: DIVIZIBILITATEA, NUMERELE PRIME și ALGORITMUL LUI EUCLID. Nu sunt doar teorie matematică – sunt instrumente practice pe care le folosești în criptografie, optimizare și multe altele.
1. Divizibilitate: “Când un Număr se Împarte Exact”
Definiție: Un număr a este divizibil cu b dacă restul împărțirii a la b este 0.
#include <iostream>
using namespace std;
int main() {
int a = 15, b = 5;
if(a % b == 0) { // Operatorul % dă restul
cout << a << " este divizibil cu " << b << endl;
} else {
cout << a << " NU este divizibil cu " << b << endl;
}
return 0;
}Proprietăți importante:
- Orice număr e divizibil cu 1 și cu el însuși
- 0 e divizibil cu orice număr (dar NU poți împărți la 0!)
- Dacă a e divizibil cu b și b cu c, atunci a e divizibil cu c
2. Numere Prime: “Atomii” Numerelor
Definiție: Număr prim = număr mai mare ca 1 care are DOAR doi divizori: 1 și el însuși.
#include <iostream>
using namespace std;
int main() {
int n = 17;
bool estePrim = true;
if(n <= 1) {
estePrim = false; // 0 și 1 nu sunt prime
} else {
// Verifică divizorii de la 2 până la n/2
for(int i = 2; i <= n/2; i++) {
if(n % i == 0) { // Dacă găsim un divizor
estePrim = false;
break;
}
}
}
if(estePrim) {
cout << n << " este numar prim!" << endl;
} else {
cout << n << " NU este numar prim!" << endl;
}
return 0;
}Optimizare 1: Verifică doar până la √n
#include <iostream>
#include <cmath> // pentru sqrt()
using namespace std;
int main() {
int n = 17;
bool estePrim = true;
if(n <= 1) {
estePrim = false;
} else {
int limita = sqrt(n); // √17 ≈ 4.12
for(int i = 2; i <= limita; i++) {
if(n % i == 0) {
estePrim = false;
break;
}
}
}
cout << n << (estePrim ? " este" : " NU este") << " prim" << endl;
return 0;
}Optimizare 2: Verifică doar numerele impare (dacă n > 2)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n = 17;
bool estePrim = true;
if(n <= 1) {
estePrim = false;
} else if(n == 2) {
estePrim = true; // 2 e prim
} else if(n % 2 == 0) {
estePrim = false; // Numerele pare mai mari ca 2 nu sunt prime
} else {
int limita = sqrt(n);
for(int i = 3; i <= limita; i += 2) { // Doar impare
if(n % i == 0) {
estePrim = false;
break;
}
}
}
cout << n << (estePrim ? " este" : " NU este") << " prim" << endl;
return 0;
}3. Generarea Numerelor Prime: “Ciurul lui Eratostene”
Algoritm inteligent pentru a găsi toate numerele prime până la o limită.
#include <iostream>
using namespace std;
int main() {
const int N = 30;
bool estePrim[N+1]; // Vector de adevăr
// Inițial, presupunem că toate sunt prime
for(int i = 0; i <= N; i++) {
estePrim[i] = true;
}
// 0 și 1 nu sunt prime
estePrim[0] = estePrim[1] = false;
// Ciurul lui Eratostene
for(int i = 2; i * i <= N; i++) {
if(estePrim[i]) { // Dacă i e prim
// Marchează multiplii lui i ca neprime
for(int j = i * i; j <= N; j += i) {
estePrim[j] = false;
}
}
}
// Afișează numerele prime
cout << "Numere prime pana la " << N << ":\n";
for(int i = 2; i <= N; i++) {
if(estePrim[i]) {
cout << i << " ";
}
}
return 0;
}4. Descompunerea în Factori Primi
Teorema fundamentală a aritmeticii: Orice număr întreg > 1 poate fi scris ca produs de numere prime.
#include <iostream>
using namespace std;
int main() {
int n = 60;
cout << n << " = ";
int copie = n;
// Împarte succesiv la factori primi
for(int divizor = 2; divizor * divizor <= copie; divizor++) {
while(copie % divizor == 0) { // Cât timp se împarte exact
cout << divizor;
copie /= divizor;
if(copie > 1) {
cout << " * ";
}
}
}
// Dacă a rămas ceva, e un număr prim
if(copie > 1) {
cout << copie;
}
cout << endl;
return 0;
}5. Algoritmul lui Euclid: “Cel Mai Mare Divizor Comun”
CMMDC = cel mai mare număr care divide două numere fără rest.
Algoritmul lui Euclid (scăderi repetate):
#include <iostream>
using namespace std;
int main() {
int a = 48, b = 18;
while(a != b) {
if(a > b) {
a = a - b; // Scade pe cel mic din cel mare
} else {
b = b - a;
}
}
cout << "CMMDC(48, 18) = " << a << endl;
return 0;
}Algoritmul lui Euclid (împărțiri repetate) – VERSIUNEA OPTIMĂ:
#include <iostream>
using namespace std;
int main() {
int a = 48, b = 18;
int copieA = a, copieB = b;
while(b != 0) {
int rest = a % b;
a = b;
b = rest;
}
cout << "CMMDC(" << copieA << ", " << copieB << ") = " << a << endl;
return 0;
}Cum funcționează:
a=48, b=18
rest = 48 % 18 = 12
a=18, b=12
rest = 18 % 12 = 6
a=12, b=6
rest = 12 % 6 = 0
a=6, b=0 → STOP
CMMDC = 66. Cel Mai Mic Multiplu Comun (CMMMC)
Formula: CMMMC(a,b) = (a × b) / CMMDC(a,b)
#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
while(b != 0) {
int rest = a % b;
a = b;
b = rest;
}
return a;
}
int main() {
int a = 12, b = 18;
int d = cmmdc(a, b);
int m = (a * b) / d; // CMMMC
cout << "CMMMC(" << a << ", " << b << ") = " << m << endl;
return 0;
}7. Numere Prime Între Ele (Relativ Prime)
Două numere sunt prime între ele dacă CMMDC = 1.
#include <iostream>
using namespace std;
int main() {
int a = 8, b = 15;
// Calcul CMMDC
int x = a, y = b;
while(y != 0) {
int rest = x % y;
x = y;
y = rest;
}
if(x == 1) {
cout << a << " si " << b << " sunt prime intre ele" << endl;
} else {
cout << a << " si " << b << " NU sunt prime intre ele" << endl;
}
return 0;
}8. Aplicații Practice
Aplicația 1: Simplificare fracție
#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 numarator = 24, numitor = 36;
int d = cmmdc(numarator, numitor);
cout << numarator << "/" << numitor << " = ";
cout << (numarator/d) << "/" << (numitor/d) << endl;
return 0;
}Aplicația 2: Verifică dacă un număr e perfect
Număr perfect = suma divizorilor săi (fără el însuși) e egală cu numărul.
#include <iostream>
using namespace std;
int main() {
int n = 28;
int sumaDivizori = 0;
for(int i = 1; i <= n/2; i++) {
if(n % i == 0) {
sumaDivizori += i;
}
}
if(sumaDivizori == n) {
cout << n << " este numar perfect!" << endl;
} else {
cout << n << " NU este numar perfect" << endl;
}
return 0;
}Aplicația 3: Numere prime gemene
Două numere prime sunt gemene dacă diferența dintre ele este 2.
#include <iostream>
#include <cmath>
using namespace std;
bool estePrim(int n) {
if(n <= 1) return false;
if(n == 2) return true;
if(n % 2 == 0) return false;
int limita = sqrt(n);
for(int i = 3; i <= limita; i += 2) {
if(n % i == 0) return false;
}
return true;
}
int main() {
cout << "Primele perechi de numere prime gemene:\n";
for(int i = 2; i <= 50; i++) {
if(estePrim(i) && estePrim(i + 2)) {
cout << "(" << i << ", " << i+2 << ")\n";
}
}
return 0;
}9. Exerciții Practice
Exercițiul 1: Completează algoritmul
int a = 36, b = 48;
int cmmdc;
// Calculează CMMDC folosind algoritmul lui Euclid
while(/* condiție */) {
int rest = /* calcul rest */;
a = b;
b = /* ce pui aici? */;
}
cmmdc = a;Soluție:
while(b != 0) {
int rest = a % b;
a = b;
b = rest;
}Exercițiul 2: Ce verifică acest cod?
int n = 29;
bool ok = true;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
ok = false;
break;
}
}Răspuns: Verifică dacă n este număr prim.
Exercițiul 3: Găsește toți divizorii unui număr
int n = 36;
cout << "Divizorii lui " << n << ":\n";
for(int i = 1; i <= /* până unde? */; i++) {
if(n % i == 0) {
cout << i << " ";
if(i != n/i) { // Evită dublarea pentru pătrate perfecte
cout << n/i << " ";
}
}
}Soluție: i <= sqrt(n) sau i * i <= n
În concluzie:
- Divizibilitatea se testează cu
%(restul împărțirii) - Numerele prime sunt fundamentul aritmeticii
- Algoritmul lui Euclid e cel mai eficient mod de a calcula CMMDC
Reguli importante:
- Orice algoritm cu numere prime începe cu verificarea cazurilor speciale (0, 1, 2)
- Pentru verificarea primalității, verifică doar până la √n
- Pentru CMMDC, folosește algoritmul lui Euclid cu împărțiri (nu scăderi)
Leave a Reply