Yeah bro… 
Thanks I m stucked at this problem since a day … and the most funny part that i already solved in OCT long 
Hi, I’m the author of this problem(in the HackerRank contest, not on Codechef !) . The solution explained by galencolin is indeed the most optimal for this problem. I saw your TLE code and the reason I guess it’s too slow is that you store all the divisors for every integer in the given range. This isn’t necessary. Instead you can save for each integer, the largest prime which divides it and use it to factorize any number in O(log(n)). Then, you can generate all divisors of a number in approximately O(n^(1 / 3)). The worst possible input for this problem would be an array all filled with highly composite numbers(the worst being 720720 with 240 factors). Still, this approach would pass this test case under 0.5 seconds.
1 Like