1388: 欧拉函数值
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：63
解决：44
题目描述
在数论，对正整数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
例如φ(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。
输出
输出正整数N的欧拉函数值。
样例输入 复制
1
2
3
4
5
6
样例输出 复制
1
1
2
2
4
2