UVa 10820 - Send A Table

Problem Link : http://uva.onlinejudge.org/external/108/10820.html

This is an straight forward Euler Totient Function problem. Given N, you have to find the sum of Totient Function of every number from 1 to N.

Now calculating Totient Function or Phi Function on each test case would be too slow. We need to pre-calculate Totient Function of every integer upto 50000. To do this, we can modify the Sieve method and utilize the following properties -