Need help with TLE

Правка en1, от sky_full_of_stars, 2021-05-30 13:57:44

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!

Теги #help, #spoj, #number theory, prime factorization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский sky_full_of_stars 2021-05-30 14:23:03 4 Tiny change: 'ity is : `N log (log N)) for sie' -> 'ity is : `O(N log(log N))) for sie'
en2 Английский sky_full_of_stars 2021-05-30 14:01:08 12 Tiny change: 'ems/DIV/) problem on SPOJ.\' -> 'ems/DIV/) bugaboo on SPOJ.\'
en1 Английский sky_full_of_stars 2021-05-30 13:57:44 603 Initial revision (published)