In line 20, you need to increment j in steps of i.

(Man, the number of times I made that mistake myself...)

Also, if you want spf[j] to be the smallest prime factor of j, line 23 should be spf[j] = min(spf[j],i).

Also, using the pow function on integers is almost never a good idea, as it uses doubles.

your code is a little messy and i wasn't able to understand it very well anyway... Euler’s Totient function Φ(n) for n is the count of numbers in {1, 2, 3..., n} that are prime to n... but instead of implementing exactly what was written above we can find Euler's product. Euler’s product formula for totient functions is equal to the product over all prime factors p of n. for ex: Φ(4)=4 * (1-1/2) =2. Φ(6)=6 * (1-1/2) * (1 – 1/3) =2. here is the code http://pastebin.com/AZZW7JS7 hope that I helped :D

http://codeforces.com/blog/entry/17881#comment-227475