What I want to point out is that never will we be multiplying all 8e4 primes, as the limit on a[i] is 10^6.
Even I cauclated primes till 10^6 using sieve but I got 50 points. http://www.codechef.com/viewplaintext/4919500
@wittyceaser
The point of log N factors is apt. However consider this - if all elements are primes in range ~ 10^6 (repetitions allowed)- then your loop was checking for all prime factors up to the number i.e ~ 8e4 factors would have been checked for each element in the worst case and N*8e4 has to time out regardless of log N factors - unless of course you modify the things.
@thezodiac1994 - Yes, I understood that mistake and hence stored the smallest prime factor for all integers upto 10^6 as precomputation, in the soln that got AC.
1 Like
yeah, I too think the approach is right. But why WA? Have you found any explanation
It seems ok when looked at first but have you checked when LCM = 1 (all are 1’s) the answer must be 0 (the corner cases).