Funció Fi d'Euler per un flux X25130

Dos nombres enters són coprimers si el seu màxim comú divisor és 1 ($mcd(a, b) = 1$), és a dir, els únics divisors comuns que tenen els dos nombres són 1 i -1. Per exemple 15 i 8 són coprimers.

La funció $\phi$ (fi) d’Euler és una funció important en la teoria de nombres i utilitza el concepte de coprimer. Si n és un nombre enter positiu, llavors $\phi(n)$ es defineix com el nombre d’enters positius menors o iguals que n i que són coprimers amb n.

Per exemple:

$\phi(36) = 12$ ja que els nombres menors o iguals a 36 i coprimers amb 36 són $12$: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 i 35.

Fes un programa que donat flux d’enters majors que 0 acabat en 0 escrigui per cada nombre del flux el seu valor de la funció $\phi$ d’Euler.

IMPORTANT! Has d’implementar i usar una funció que donat un nombre natural retorni el valor de la funció $\phi$ per aquest nombre.

Entrada

L’entrada consisteix en un flux d’enters majors que 0 acabat en 0.

Sortida

Mostra per cada nombre del flux en una línia:

• el nombre del flux

• dos punts

• un espai

• el valor de la funció $\Phi$ per aquest nombre.

Per obtenir més detalls sobre la sortida consulta els jocs de proves públics.