This question confused me during the contest. I thought maybe if I go till $$$1e6$$$ I should be fine, but I got a TLE, no surprises. Then I optimized the code using two pointers, added in some memoization, and prime factors, and tried again with $$$1e6$$$, It failed no surprise. By this time I realized maybe if I tried the "normal" way till $$$1e4$$$ should work and I got accepted.

But "craziness" started after the contest when I tried to submit my optimized code with a limit of $$$1e4$$$, and to my surprise it passed and it was faster than the C++ submission! Curiously, I increased the limit to $$$1e5$$$ and it passed again but it was pretty close to a TLE.

Exhibit: 216349728

I tried to explain what I have done, but if somebody could help me point out how this code could run even till $$$1e5$$$ I'd appreciate it.

Explained Code: 216355374

Please excuse my English :}