Se citeste un numar natural n. Folosind ciurul lui Euler (o varianta a ciurului lui Eratostene), determinati, pentru fiecare numar de la 1 la n, valoarea functiei indicator a lui Euler, phi(i): numarul de numere din intervalul [1, i] care sunt prime cu i.
- Date de intrare
- Pe prima linie se afla numarul natural n.
- Date de iesire
- Afiseaza pe o singura linie n numere separate prin spatiu: phi(1), phi(2), ..., phi(n), in aceasta ordine.
- Restrictii
- 1 <= n <= 2000
Exemple
Exemplul 1
Intrare
10
Iesire
1 1 2 2 4 2 6 4 6 4
Exemplul 2
Intrare
1
Iesire
1