Numere și divizibilitate la atestatul de informatică

Totul pleacă de aici. Pentru două numere întregi:

Atenție: în C++, / între două numere int dă împărțire întreagă. 7 / 2 este 3, nu 3.5. Dacă unul dintre operanzi e real (7 / 2.0), rezultatul devine real — sursa clasică de erori.

Testul de divizibilitate

if (n % d == 0)   // d il imparte exact pe n

Aceasta este singura condiție de care ai nevoie pentru divizori, numere prime, numere perfecte și c.m.m.d.c. Dacă restul e zero, împărțirea e exactă.

Extragerea cifrelor

Combinând cele două operații, „desfaci" un număr cifră cu cifră:

n % 10        // ultima cifra
n / 10        // numarul fara ultima cifra

Repetând până când numărul ajunge 0, treci prin toate cifrele, de la dreapta spre stânga:

3815 → cifra 5, ramane 381
 381 → cifra 1, ramane 38
  38 → cifra 8, ramane 3
   3 → cifra 3, ramane 0   ← stop

Aplicat direct la suma cifrelor și la produsul cifrelor.

Un număr este prim dacă are exact doi divizori: 1 și el însuși. 0 și 1 nu sunt prime.

bool estePrim(int n) {
    if (n < 2) return false;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) return false;
    return true;
}

De ce d * d <= n

Nu e nevoie să cauți divizori până la n, pentru că divizorii vin în perechi. Pentru n = 36:

1 × 36        6 × 6   ← mijlocul, adica radical din 36
2 × 18
3 × 12
4 × 9

Orice divizor mai mare decât √n are deja o pereche mai mică decât √n. Dacă n-ai găsit niciunul până la √n, nu mai există niciunul nici după. Pentru n = 1.000.000 înseamnă 1000 de pași în loc de un milion.

Se scrie d * d <= n, nu sqrt(n) — sqrt lucrează cu numere reale și poate da 5.999999 în loc de 6, ratând ultimul divizor.

Aceeași buclă, două rezultate diferite. Diferența stă în limita superioară:

// toti divizorii, inclusiv n
for (int d = 1; d <= n; d++)
    if (n % d == 0) c++;

// doar divizorii proprii (fara n insusi)
for (int d = 1; d <= n / 2; d++)
    if (n % d == 0) s += d;

Niciun divizor propriu al lui n nu poate depăși n / 2 — de aceea a doua buclă se oprește acolo. Confuzia între cele două limite e una dintre cele mai frecvente greșeli.

Un număr este perfect dacă e egal cu suma divizorilor săi proprii. Primele două sunt 6 (1+2+3) și 28 (1+2+4+7+14).

bool estePerfect(int n) {
    if (n < 2) return false;
    int s = 0;
    for (int d = 1; d <= n / 2; d++)
        if (n % d == 0) s += d;
    return s == n;
}

Un număr e palindrom dacă rămâne același citit invers: 8, 121, 3003.

bool estePalindrom(int n) {
    int inversat = 0, copie = n;
    while (copie != 0) {
        inversat = inversat * 10 + copie % 10;
        copie /= 10;
    }
    return inversat == n;
}

Linia-cheie se citește: „împinge cifrele deja adunate cu o poziție la stânga, apoi pune ultima cifră a lui copie pe locul rămas liber."

Se lucrează pe o copie, nu pe n — bucla consumă valoarea, iar la final ai nevoie de n intact pentru comparație. Este greșeala numărul unu la această categorie.

int cmmdc(int x, int y) {
    if (y == 0) return x;
    return cmmdc(y, x % y);
}

Ideea: c.m.m.d.c. al lui x și y este același cu cel al lui y și restul împărțirii lui x la y. Dacă un număr îi împarte exact și pe x, și pe y, atunci împarte exact și restul.

cmmdc(48, 36) → 48 % 36 = 12 → cmmdc(36, 12)
cmmdc(36, 12) → 36 % 12 = 0  → cmmdc(12, 0)
cmmdc(12, 0)  → return 12

Nu contează ordinea argumentelor: cmmdc(36, 48) face un pas în plus și ajunge la același lucru.

Pentru un vector întreg, se aplică în lanț, pentru că operația e asociativă: d = cmmdc(d, x[i]) la fiecare pas, pornind de la d = x[0].

Dacă reții un singur lucru din pagina asta, reține-l pe acesta. Problemele nu sunt rezolvări diferite, ci aceleași trei structuri combinate.

1. Funcție de test + buclă

Scrii o funcție care răspunde true/false pentru un element, apoi o apelezi pentru fiecare. Funcționează identic la prime, perfecte, palindroame.

for (int i = 0; i < n; i++)
    if (esteCeva(x[i])) { /* ... */ }

2. Flag sau contor pentru cazul gol

Aproape toate enunțurile cer NU EXISTA când nu s-a găsit nimic. Nu poți ști asta decât după ce ai parcurs tot:

bool gasit = false;              // sau: int cate = 0;
for (...)
    if (...) { cout << x[i] << " "; gasit = true; }
if (!gasit) cout << "NU EXISTA";

Când enunțul cere câte sunt, contorul înlocuiește flagul — îți dă și răspunsul, și informația „există sau nu".

3. Rezultat parțial acumulat

Pornești de la primul element și îl combini pe rând cu următoarele: d = cmmdc(d, x[i]). Aceeași structură funcționează la sumă, maxim sau c.m.m.m.c.