练习专区

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。 例如φ(8)=4，因为1,3,5,7均和8互质。 φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn), 其中p1, p2……pn为x的所有质因数，x是不为0的整数。 φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 注意：每种质因数只一个。 比如12=2*2*3，那么φ（12）=12*（1-1/2）*(1-1/3)=4 若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。 现在请你编程求给定正整数N的欧拉函数值。

问题的输入有多组，每组一行。每行一个正整数N。

输出正整数N的欧拉函数值。

1
2
3
4
5
6

1
1
2
2
4
2