I was trying to solve this problem on SPOJ.

My approach is fairly simple. I pre-calculate all prime numbers, smallest prime factor, and all divisors in sieve() first.

Then for each i in [1,maxN) I calculate the number of divisors for each 'i' and verify if its a valid number in O(1).

total complexity is : N log (log N)) for sieve + O(N log(N) to check number of divisors

My solution which TLE'd.

I'm not able to figure out what I'm missing here. Can someone please help me with this?

Thanks!