Tell me where you find difficulty to understand code?
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.
1 Like
Great analogy 
@likecs : P*sqrt(N) exceeds 10^7.I Why doesn’t this give memory limit exceeded? What is the upper bound on the size of the array?