Bucle imbricate și tiparele clasice

Testul de număr prim

Tiparul care apare constant la BAC:

#include <iostream>
using namespace std;

int main() {
    int n = 97;
    int prim = 1;
    if (n < 2) prim = 0;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) { prim = 0; break; }
    cout << prim;
    return 0;
}

Optimizarea d * d <= n (verifici doar până la radical) e standard; 1 și 0 NU sunt prime.

Urmărire pentru n = 29: d = 2, 3, 4, 5 (25 ≤ 29), niciun divizor → prim = 1 ✓.

Suma și numărul divizorilor

#include <iostream>
using namespace std;

int main() {
    int n = 28;
    int s = 0, nr = 0;
    for (int d = 1; d <= n; d++)
        if (n % d == 0) { s += d; nr++; }
    cout << s << " " << nr;
    return 0;
}

Pentru n = 12: divizorii 1, 2, 3, 4, 6, 12 → nr = 6, s = 28.

Bucle imbricate: numărarea perechilor

Câte perechi (i, j) cu $1 \le i < j \le n$ au suma pară?

#include <iostream>
using namespace std;

int main() {
    int n = 6;
    int nr = 0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if ((i + j) % 2 == 0) nr++;
    cout << nr;
    return 0;
}

Pentru n = 4: perechile (1,3), (2,4) → nr = 2. Regula: suma pară = ambele pare sau ambele impare.

Numărul de pași la bucle imbricate

#include <iostream>
using namespace std;

int main() {
    int n = 4;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << i * j << " ";
        cout << "\n";
    }
    return 0;
}

execută corpul de $n^2$ ori; cu j = i + 1 la start: $\dfrac{n(n-1)}{2}$ ori (perechile). La subiectul cu "de câte ori se execută", astea două formule acoperă majoritatea cazurilor.

Greșeli frecvente

1. Testul de prim fără cazul n < 2: 1 nu e prim.
2. La perechi cu i < j, bucla interioară pornește de la i + 1, nu de la 1 (altfel numeri dublu).
3. d * d <= n, nu d <= n / 2: a doua e corectă dar mai lentă și diferă la urmărire.