Să se afişeze toate numerele mai mici sau egale cu n, care au exact 3 divizori

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.