De ce contează?
Ai 12 bomboane și vrei să le împarți în grupe egale, fără să rămână niciuna. Câte variante ai? Grupe de 1, 2, 3, 4, 6 sau 12 — exact divizorii lui 12. Găsirea eficientă a divizorilor este una dintre problemele fundamentale ale olimpiadei de informatică.
Definiție
d este divizor al lui n dacă n % d == 0 (împărțirea este exactă, fără rest). În același timp, n este multiplu al lui d.
Exemplu: Divizorii lui 12 sunt 1, 2, 3, 4, 6, 12.
Varianta naivă — O(n)
for (int d = 1; d <= n; d++) {
if (n % d == 0) cout << d << " ";
}Funcționează, dar pentru n = 1.000.000 face un milion de operații. Există o cale mult mai rapidă.
Varianta eficientă — O(√n)
Observație cheie: Dacă d divide n, atunci și n/d divide n. Cei doi divisori vin în perechi, iar cel mai mic din pereche este ≤ √n. Deci nu trebuie să verifici mai departe de √n:
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
cout << d << " "; // d este divizor
if (d != n / d)
cout << n / d << " "; // n/d este celalalt divizor din pereche
}
}Condiția d * d <= n este preferată lui d <= sqrt(n) în concursuri: evită calculul virgulă mobilă și erorile de rotunjire care pot apărea la pătrate perfecte (de exemplu, sqrt(9) poate da 2.9999... în unele implementări).
Implementare C++ — complet
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
cout << "Divizorii lui " << n << ": ";
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
cout << d << " ";
if (d != n / d)
cout << n / d << " ";
}
}
cout << endl;
return 0;
}Exemplu: Input 12 → 1 12 2 6 3 4
(Divizorii apar în ordinea în care sunt descoperiți, nu sortat — dacă ai nevoie de ei sortați, stochează-i într-un vector.)
Numărarea divizorilor
int nr_div = 0;
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
nr_div++;
if (d != n / d) nr_div++;
}
}Complexitate
| Variantă | Timp | Spațiu |
|---|---|---|
| Naivă (până la n) | O(n) | O(1) |
| Eficientă (până la √n) | O(√n) | O(1) |
Greșeala 1: Scrii d <= sqrt(n) cu tipul double. Erorile de rotunjire pot face ca un pătrat perfect (ex. n=9, d=3) să nu treacă condiția. Folosește d * d <= n.
Greșeala 2: Uiți condiția d != n / d pentru pătrate perfecte. Pentru n=9 și d=3 ai 3 = 9/3 — dacă afișezi și n/d, obții 3 de două ori.
Greșeala 3: Pornești de la d = 0. n % 0 provoacă eroare de împărțire prin zero. Pornește mereu de la d = 1.