Rezolvare PBinfo #3289

Cerința

Indicatorul lui Euler, φ(n) – uneori numită funcția phi, este folosit pentru a determina câte numere mai mici decât n sunt relativ prime cu n. De exemplu, cum 1, 2, 4, 5, 7 și 8 sunt toate mai mici decât 9 și relativ prime la 9, φ(9)=6.

Se poate vedea că n=6 produce valoarea maximă n/φ(n) pentru n ≤ 10.

Se consideră un șir de numere naturale mai mari decât 1, numere formate din cel mult 9 cifre. Să se scrie un program care determină dintre acestea numărul n pentru care raportul n/φ(n) are valoare maximă. În cazul în care sunt mai multe valori pentru care raportul n/φ(n) este maxim se va afișa prima dintre ele.

Date de intrare

Fișierul de intrare maxprimeintreele.in conține pe prima linie cel mult 10000 numere naturale din intervalul [2,999999999] separate prin spații.

Date de ieșire

Fișierul de ieșire maxprimeintreele.out va conține pe prima linie numărul k, reprezentând numărul n pentru care raportul n/φ(n) are valoare maximă.

Restricții și precizări

• numerele din fișierul de intrare sunt din intervalul [2, 999999999]

Exemplu:

maxprimeintreele.in

2 3 4 5 6 7 8 9 10

maxprimeintreele.out

6

Explicație

Dintre numerele aflate în fișierul de intrare, numărul 6 are raportul n/φ(n) cu valoare maximă și anume 3.