🪩 Programare C++: Numere Prime și Divizori

🪩 Programare C++: Numere Prime și Divizori

Verificarea unui număr prim în C++

Verificarea dacă un număr este prim este o problemă comună în programare. Un număr este considerat prim dacă are exact doi divizori: 1 și el însuși. Algoritmul de verificare a unui număr prim începe prin testarea cazurilor simple, urmată de o verificare iterativă pentru a vedea dacă numărul se împarte exact la vreun alt număr între 2 și rădăcina pătrată a acestuia.

Algoritmul începe prin eliminarea numerelor mai mici decât 2, deoarece acestea nu pot fi prime. Următorul pas este verificarea dacă numărul este 2, singurul număr prim par. Apoi, se elimină toate numerele pare mai mari decât 2. În final, algoritmul verifică dacă numărul este divizibil de vreun alt număr impar până la rădăcina pătrată a numărului. Dacă nu găsește niciun astfel de divizor, numărul este prim.

Determinarea divizorilor unui număr în C++

Divizorii unui număr sunt toți acei numere care împart numărul respectiv exact, fără rest. Determinarea divizorilor unui număr poate fi realizată în două moduri: o metodă neeficientă, care verifică fiecare număr de la 1 la n, și o metodă mai eficientă, care utilizează doar divizorii până la rădăcina pătrată a numărului.

Varianta 1: Metoda Neeficientă

Această metodă parcurge toate numerele de la 1 la n și verifică dacă fiecare dintre ele este un divizor. Dacă este, divizorul este adăugat la suma divizorilor.

Deși simplă, această metodă este ineficientă pentru numere mari, deoarece necesită verificarea fiecărui număr până la n.

Varianta 2: Metoda Eficientă

O metodă mai eficientă de determinare a divizorilor este aceea de a parcurge doar numerele până la rădăcina pătrată a numărului. Pentru fiecare divizor găsit, se poate determina și perechea sa, reducând astfel numărul total de pași.

Această metodă este mult mai rapidă, deoarece reduce numărul de operații necesare pentru a găsi toți divizorii unui număr. În loc să parcurgă toate numerele până la n, algoritmul se oprește la rădăcina pătrată a numărului și determină perechile de divizori.

Concluzie

Aceste tehnici sunt esențiale pentru înțelegerea matematicii de bază aplicate în programare și pot fi extinse pentru a rezolva probleme mai complexe.