@shubamg First see the point that an element can be divided only log(n) times cause after that it becomes 1.

So how I approached this problem is to first maintain a range I calculate largest smallest prime factor and maintain it in a segment tree. Now perform point updates on all points on ranges. However don’t go inside segments which have the largest smallest prime factor as 1 as you cannot do any operation for 1.

Now you notice that each range can be called atmost logm times and there are nlogn ranges.So it is O(Nlog(m)log(n)). For each query it is log(n). So the extra Qlogn factor.

I would like to give a proof of time complexity of the algorithm stated in the editorial. I had a doubt earlier that there may be updates on the ranges which have all their members equal to 1. This will not decrease the value of any array element but still consume extra time. But we can still use amortised analysis to prove the time complexity of the algorithm.

So let the processing at any node of the segment tree may take at max \alpha time. Consider the potential function \phi = 2*\alpha*\sum_{n \in \textrm{node}} \sum_{i=l(n)}^{r(n)} f(A[i]). Here n can be any node of segment tree which covers range [l(n),r(n)]. f(x) gives number of prime factors of x e.g. f(2^n)=n, f(6)=2.

Using this \phi, we can prove the desired time complexity of the algorithm.

Increase the size of your segment tree and other arrays accordingly! You are trying to access an element which is more than size of the arrays you have made.