Problem H: 欧拉函数

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $238$ 正确数量 $198$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数论
给定一个大于$1$,不超过$2000000$的正整数$n$,输出欧拉函数,$\phi(n)$的值。
如果你并不了解欧拉函数,那么请参阅提示。

在给定的输入文件中进行读入: 
一行一个正整数$n$。 

将输出信息输出到指定的文件中: 一行一个整数表示$\phi(n)$。
17
16
欧拉函数$\phi(n)$是数论中非常重要的一个函数,其表示$1$到$n$之间,与$n$互质的数的个数。显然的,我们可以通过定义直接计算$\phi(n)$。 当然,$\phi(n)$还有这么一种计算方法。 首先我们对n进行质因数分解,不妨设$n={p_1}^{a_1} * {p_2}^{a_2} * ... *{p_k}^{a_k} $ (这里$a^b$表示$a$的$b$次幂,$p_1$到$p_k$为$k$个互不相同的质数,$a_1$到$a_k$均为正整数),那么 $\phi(n)=n(1-(1/p_1))(1-(1/p_2))....(1-(1/p_k)) $ 稍稍化简一下就是 $\phi(n)=n(p_1-1)(p_2-1)...(p_k-1)/(p_1*p_2*...*p_k) $ 计算的时候小心中间计算结果超过int类型上界,可通过调整公式各项的计算顺序避免(比如先做除法)!