>504
そうでした。
素数べきに関してはφ(p^k)=p^k-p^{k-1}でgcd(a,b)=1ならφ(ab)=φ(a)φ(b)と書ける事から
n=p_1^r_1p_2^r_2・…・p_m^r_mなら
φ(n)=Π_[i=1..m] (p_i^r_i-p_i^{r_i-1})となりますね。