Efficient way to find number of divisors for problem D1

Problem code

My solution

I am getting a TLE error. I am following the tutorial for it. I think my number of factors generation is slow. Is there any other problem? What is the most optimized method for generating the number of factors?

p.s. sqrt(n) approach gives TLE (as mentioned in editorial too)

Brother, it is very effective way to calculate factors, you may be doing some mess with it.

Kindly refer to this link, for detail, and study completely (don’t skip :slight_smile: )

Integer Factorization

Hi dragonemperor,

i didn’t solve this problem but i can tell something about your solution

in your prime generator function you have j = i+i so make it j=i*i .

and rather than generating all primes upto MAX just generate upto sqrt(MAX) only because if number have no factor in range ( 2 to sqrt(n) ) then that number will be prime and after removing all factor less than sqrt(n) if that number is still greater than sqrt(n) means current value is prime.

1 Like

please look at this link and tell me why I got WA…D1

I optimised my sieve but still am getting TLE

https://www.codechef.com/viewsolution/7775402