SPOJ Problem Set (main) 1927. Funkcja phi Eulera Problem code: EULER_PH

Napisz program, który dla danej liczby naturalnej n obliczy wartość phi(n), gdzie phi(n) jest funkcją Eulera (tocjent) i oznacza liczbę liczb względnie pierwszych z n, mniejszych od n. Na przykład phi(6)=2 Bo względnie pierwsze z 6 są tylko liczby 1, 5

Wejście

W pierwszym wierszu dana jest liczba T - ilość przypadków testowych (0< T< 30). Każdy przypadek podany jest w jednym wierszu zawierającym liczbę n (1 < n < 2*10^9).

Wyjście

Dla każdego przypadku testowego, wypisz w osobnym wierszu wartość phi(n).

Przykład

Wejście:

2

6

100

Wyjście:

2

40

Zachęcam do przeczytania moich notatek: Funkcja phi Eulera Added by:

Rafał Nowak

Date:

2007-10-18

Time limit: 1s Source limit:1000B

Languages: All Resource:

www.rafalnowak.pl 1