Question

Dorel
este pasionat de feng shui. Astfel, pentru a-şi crea un cadru adecvat meditaţiei, s-a hotărât să scrie pe pereţii casei numere care au un număr prim de divizori. El a găsit n numere, însă nu ştie să le aleagă pe cele potrivite.

Cerința
Se dau n numere naturale. Aflaţi câte dintre acestea au un număr prim de divizori.

Date de intrare
Fișierul de intrare prim013.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire
Fișierul de ieșire prim013.out va conține pe prima linie numărul de numere care au un număr prim de divizori.

Restricții și precizări
1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000

Exemplu
prim013.in

5
1 3 6 9 625
prim013.out

3
Explicație
Numerele 3,9,625 au 2,3 respectiv 5 divizori, numărul divizorilor fiind prim. În total sunt 3 numere cu numărul divizorilor prim.

Answer 1

Programul : https://pastebin.com/B7d5W2eE

Daca ai luat problema de pe pbinfo, metoda directa de aflarea numarului de divizori, dupa care verificarea acestuia daca e prim, obtine punctaj maxim, doar ca din cauza limitei de timp trebuie de folosit functii rapide. Functia nrdiv din program actioneaza dupa regula ca daca avem un numar si reprezentarea lui prima : x=p₁ᵃp₂ᵇ...pₓⁿ, at nr de divizori vor fi (a+1)*(b+1)*...*(n+1), adica la exponentii factorilor adaugam unu si le inmultim. Functia prim e aceeasi parcurgere de la 1 la n, doar ca se omit din start numerele pare si se controleaza doar cele impare (din 2 in 2).