Problem link:

My Approach:

- Use Euler Totient Functions to get the number of co-primes
- Find the Total No. of Divisors of N ----------> O(sqrt(N))
- [ N - Euler_Totient(N) - Total_Divisors(N) ] is the answer.

Still got partially correct & TLE.

My best guess is that the time-consuming part is STEP 2. How can I improve the step 2?

Or, perhaps should I change my approach?

P.S. the contest is already over!