Rezolvare PBinfo #2568

Definim prin număr cubprim, numărul natural obținut dintr-un număr prim la puterea a treia.

Cerința

Se dă un șir de N numere naturale oarecare \({x}_{1}, {x}_{2}, … {x}_{n}\).
a) Să se afișeze M – numărul de numere cubprim.
b) Să se afișeze pe următoarele M linii, descrescător după valoarea numărului cubprim de la cerința a), poziția pe care se află acest număr, numărul prim din care este format, precum și numărul cubprim astfel găsit.

Date de intrare

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

Date de ieșire

În fișierul cubprim.out se afișează pe prima linie numărul de elemente găsite conform cerinței a).
Pe următoarele M linii se afișază elementele găsite, separate printr-un spațiu conform cerinței b).

Restricții și precizări

• 1 ≤ N ≤ 200.000
• 0 ≤ \({x}_{1}, {x}_{2}, … {x}_{n}\) < \({2}^{64}\)
• pentru numerele cubprim cu aceeași valoare se afișează mai întâi numărul cubprim aflat pe poziția mai mică.
• se garantează că în fiecare test va exista cel puțin un număr format din cubul unui număr prim.

Exemplu:

cubprim.in

10
5 23 8 7 32 121 27 14 64 8

cubprim.out

3
7 3 27
3 2 8
10 2 8

Explicație

a) Avem 3 numere care respectă cerința : 8, 27 și 8. Unde 8 este cubul lui 2 și 27 al lui 3. Se observă că în șir apare și 64 care este cubul lui 4 dar numărul 4 nu este prim.
b) Cubul cel mai mare format dintr-un număr prim este 27, poziția lui în șir este 7, urmat de numărul prim 3 care formează acest cub (3 * 3 * 3 = 27). Ultimele două linii sunt formate de numărul 8 găsit de două ori in șir, prima dată pe poziția 3 și apoi pe poziția 10.