Divizori — AlgoClar

De ce contează?

Vrei să aranjezi 12 scaune în rânduri egale. Poți face 1×12, 2×6 sau 3×4 — perechi de numere care înmulțite dau 12. Exact astea sunt divizorii: numerele care „încap" exact în 12, mereu în perechi.

Ce este un divizor

d este divizor al lui n dacă n se împarte exact la d, adică n % d == 0. Divizorii lui 12 sunt: 1, 2, 3, 4, 6, 12.

Varianta simplă: O(n)

Verificăm fiecare candidat de la 1 la n:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int d = 1; d <= n; d++) {
        if (n % d == 0) {
            cout << d << " ";    // 12 -> 1 2 3 4 6 12
        }
    }
    return 0;
}

Corect, dar pentru n mare (un miliard) face un miliard de pași — prea lent.

Ideea cheie: divizorii vin în perechi

Dacă d divide n, atunci și n / d divide n. Cei doi sunt o pereche așezată simetric față de √n:

Divizorii lui 12, aranjați. Perechile sunt (1,12), (2,6), (3,4) — una sub √12 ≈ 3.46, cealaltă peste. E destul să-i găsești pe cei mici.

Deci e suficient să cauți d doar până la √n: pentru fiecare d găsit, ai gratis și perechea n / d.

Varianta rapidă: O(√n)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cate = 0;
    for (int d = 1; (long long)d * d <= n; d++) {   // d pana la radical din n
        if (n % d == 0) {
            cate++;                  // divizorul d
            if (d != n / d) {        // evitam dublarea la patrat perfect
                cate++;              // perechea n/d
            }
        }
    }
    cout << "Numar de divizori: " << cate << "\n";   // 12 -> 6
    return 0;
}

Observația-cheie

Condiția d * d <= n e echivalentă cu d <= √n, dar evită calculul cu sqrt (care lucrează cu numere reale și poate da erori de rotunjire). Scrie (long long)d * d ca să nu se spargă produsul la n mare.

De ce verificarea `d != n / d`

La un pătrat perfect (ex. 36), când d = 6 avem n / d = 6 — aceeași valoare. Fără verificarea d != n / d, l-ai număra de două ori. Pentru orice alt divizor, perechea e diferită și o adaugi normal.

Complexitate

Variantă	Timp	Spațiu
naivă (1..n)	O(n)	O(1)
cu perechi (1..√n)	O(√n)	O(1)

Pentru n = 10⁹: varianta naivă face ~10⁹ pași (prea lent), cea cu perechi doar ~31.000.

Greșeli frecvente

Capcane reale la divizori:

Bucla până la n: corectă, dar O(n) — depășește timpul pentru n mare. Mergi până la √n.
Overflow în condiție: d * d în int se sparge pentru d peste ~46.000. Scrie (long long)d * d <= n.
Dubla numărare la pătrate perfecte: uiți d != n / d și 36 iese cu un divizor în plus.
sqrt în condiție: d <= sqrt(n) poate rata sau adăuga un divizor din cauza rotunjirii. Preferă d * d <= n.

De reținut

d divizor al lui n ⟺ n % d == 0.
Divizorii vin în perechi (d, n/d) → cauți doar până la √n, cost O(√n).
La pătrate perfecte, perechea coincide — nu număra divizorul de două ori.