 # need help in optimising euler totient problem

Can someone help me with this [problem]. Here is my


. I am doing queries in O(1) but still getting TLE.Any help is appreciated.

I don't have enough reputation that's why I could not upload the image of the [problem] as the question demands login to see it. :(

I am using prefix sum of scores' square to answer queries.

: http://lightoj.com/volume_showproblem.php?problem=1007

NO. of primes less than n are approximately \frac{n}{logn}. Therefore time complexity of your tot function is O(\frac{n}{logn}) as the loop runs \frac{n}{logn} (no. of primes less than n) times.
Now you call your tot() function n times. So the overall time complexity of your program is O(\frac{n^2}{logn}), which surely won’t pass.

Instead, you can calculate totient function in the sieve() itself which will have a time complexity of just O(n log log n) which is very efficient.

sieve()
for i=1 to n
phi[i] = i;
for(int i=2;i<=n;++i)
if(phi[i] == n-1)                        // i is prime
for(int j=i*i;j<=n;j+=i)
phi[j] = phi[j]*(i-1)/i;          // i is a prime factor of j
1 Like

Thanks for the effort but can you give a little example of how your code optimises runtime . I am new here. 