Again, pre computing the answers is a good idea, we simply keep an array ANS where ANS[i] shows the answer for I. Now how do we construct ANS? There is a good formula for a number of divisors of a number. If the prime factorization of a number is p1^a1*p2^a2*...*pn^an then the number of divisors is (a1+1)*(a2+1)*...*(an+1). Factorizing the number to prime factors takes sqrt(N) ish time. And also it's a very good idea to store the prime numbers before trying to factorize the number, it will give us some speed boost, and we will do that with the sieve of Eratostenes, if you need more info about the sieve you can find it in this blog in the "Algoruthms" Section.'
No comments:
Post a Comment