Rezolvare PBinfo #3311

Numerele regulate sunt numerele ce au ca factori primi doar numerele 2, 3 și 5. Primele 20 de numere regulate sunt: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36.

Cerința

Fișierul de intrare nrreg.in conține pe prima linie numărul natural n (n<=10000). Scrieți un program care determină:

• cel de-al n-lea număr regulat, x;
• cel mai mic divizor d al lui x cu proprietatea că p = x / d este pătrat perfect;
• valoarea p.

Programul va scrie în fișierul nrreg.out valorile x d p, separate prin câte spațiu.

Exemplu: dacă n=10, al zecelea număr regulat este x=12; d=3, iar p=4.

Date de intrare

Fișierul de intrare nrreg.in conține pe prima linie numărul natural n.

Date de ieșire

Fișierul de ieșire nrreg.out va conține pe prima linie numărul x d p, separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 10000
• prin convenție s-a stabilit că numărul 1 face parte din șirul numerelor regulate.

Exemplul 1:

nrreg.in

10

nrreg.out

12 3 4

Explicație

Al zecelea număr regulat este 12; numărul minim care îl divide pe 12 pentru a obține un pătrat perfect este 3 iar pătratul perfect este 4.

Exemplul 2:

nrreg.in

5

nrreg.out

5 5 1

Explicație

Al cincilea număr regulat este 5; numărul minim care îl divide pe 5 pentru a obține un pătrat perfect este 5 iar pătratul perfect este 1.

Exemplul 3:

nrreg.in

20

nrreg.out

36 1 36

Explicație

Al douăzecilea număr regulat este 36; numărul minim care îl divide pe 36 pentru a obține un pătrat perfect este 1 iar pătratul perfect este 36.