Cum funcționează
Rezolvarea e directă: pentru fiecare număr până la n, numeri divizorii și îl afișezi dacă are
exact 3. Numărarea divizorilor e aceeași buclă de la
numărul perfect, doar că numeri în loc să aduni.
Limita n < 500 din enunț e un semnal important: e mic intenționat, ca varianta simplă să
treacă fără probleme. Nu are rost să optimizezi.
Merită însă să înțelegi de ce ies exact numerele din exemplu, pentru că e o întrebare clasică la
oral. Un număr cu exact 3 divizori este întotdeauna pătratul unui număr prim:
4 = 2² → divizorii 1, 2, 4
9 = 3² → divizorii 1, 3, 9
25 = 5² → divizorii 1, 5, 25
49 = 7² → divizorii 1, 7, 49
Explicația: orice număr are măcar divizorii 1 și pe el însuși — ăștia sunt doi. Ca să existe
exact încă unul, mai trebuie fix un divizor „la mijloc", iar asta se întâmplă numai când numărul e
p × p, cu p prim. Dacă ar fi p × q cu p diferit de q, ar apărea doi divizori în plus, nu
unul.
Din observația asta iese și o variantă alternativă — parcurgi numerele prime p cu p * p <= n și
afișezi p * p. E mai rapidă, dar la n < 500 diferența e invizibilă, iar varianta cu numărarea
divizorilor e mai aproape de ce cere enunțul literal.
Greșeli frecvente
i < n în loc de i <= n — enunțul spune „mai mici sau egale cu n". Dacă n e chiar
49, trebuie afișat.- Numărarea divizorilor până la
n / 2 — corectă pentru divizorii proprii, dar aici n
însuși se numără, deci bucla merge până la n. Confuzia cu problema numerelor perfecte e foarte
frecventă.
- Pornirea de la
d = 2 — 1 e divizor și trebuie numărat, altfel niciun număr nu ajunge la 3.
- Căutarea doar printre numerele prime — numerele prime au exact 2 divizori, nu 3. Cele
căutate sunt pătratele lor.