Mine solution is a simple one. Just use the sqrt trick for summation between ranges. As in this problem, along with ranges, another query pair (X, Y) is added, maintain prefix sum for it over the sqrt-root ranges. 2 things are needed to be taken care of in this method:
Memory size. Naively is it Max(A_i) * No of Blocks, but it can be compressed to P * No.of.Blocks, where P is number of primes below 10^6.
Choosing an efficient block size would be either of (R, L) pair or (X, Y) pair. My solution timed out for (R, L) pair but passed for (X, Y) pair.
Hey, This problem can be solved using just segment tree, The approach is we can store the prime factors as key and their count as the value in the leaf nodes of segment tree and we can merge the same keys and add up their count. I have written a blog which explains my solution, have a look here. Link to the blog.
We can also view this problem as finding the number of points inside a rectangle.
The points are of the form (X,Y) where X is the index of the number arr[X] in the array and for each X,
Y’s are the Prime factors of arr[X].
The queries are of the form L,R,X,Y which translate to the rectangle formed by x=L,x=R,y=X,y=Y.
So we have points in 2d plane and queries are given by rectangles. we have to find the number of points inside this rectangle(including the border) which can be done by segment trees, Square root decomposition etc.
Is this approach similar to(In general) maintaining a cumulative frequency of primes then binary searching the indices for x and y ? and doing this thing with either Segment tree/square root decomposition ?