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.