Funkcja φ (czyt. "phi") Eulera lub tocjent, to funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej n liczbę liczb względnie z nią pierwszych nie większych od n. Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.
Oto kilka własności tej funkcji:
1. Jeśli p jest liczba pierwszą, to: φ(p)=p-1 2. Jeśli m i n są względnie pierwsze, to: φ(m*n)=φ(m)*φ(n) 3. Jeśli p jest liczbą pierwszą i n=pk, to: φ(n)=pk-1*(p-1) 4. φ(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk), gdzie p1, p2, ..., pk są wszystkimi czynnikami pierwszymi liczby n liczonymi bez powtótrzeń
Napisz program, który dla danych liczb naturalnych wyznaczy wartość funkcji φ Eulera.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n
z zakresu
W każdym z kolejnych n wierszy zapisano po jednej liczbie całkowitej
z zakresu 2..2*109.
Wyjście zgodne z przykładem.
Dla danych podanych na wejściu:
4 6 6 2 4
Poprawną odpowiedzią jest wyjście:
2 2 1 2
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :