### PROBLEM LINK:

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Segment Trees, Binary Search

### PROBLEM:

Given an array a of N integers and Q queries where each query provides you with four integers L, R, X and Y.

For each query, output the value of F(L, R, X, Y) as count the number of primes that lie in the range x to y and that divides the number between the range l to r of A[i].

F(L, R, X, Y)

```
result := 0
for( i = X to i = Y ) {
if( isPrime(i) ) {
for( j = L to j = R ) {
number := a[j]
exponent := 0
while( number % i == 0 ) {
exponent := exponent + 1
number := number/i
}
result := result + exponent
}
}
}
return result
```

### QUICKK EXPLANATION:

If you are new to Segment Trees then THIS will definitely help you get over segment tree.This is by far the best blog i have came across while reading segment trees. But if you still face hard time understanding this then you can refer to This and This videos.

This problem basically boils down to count the number of primes that lie in the range x to y and that divides the number between the range l to r of A[i]. So for that we can keep track of the prime factors of every A[i].

### EXPLANATION:

As 2<=A[i]<=10^6 so maximum number of prime factors can be 2x3x5x7x11x13x17x19 which exceeds 10^6. So what i did here is calculated the prime factors of all the input numbers and pushed them into an array of vectors named v. Each vector in this array stores the prime factors of the corresponding to A[i]. Now i created a segment tree using this array of vectors. While merging 2 nodes all the prime factors are inserted in sorted order of a leaf node in the segment tree so that we can do binary search on the prime factors to count them between the numbers x and y. This is my first blog, kindly point out the mistakes if any.

Coming to the code here i have taken my node as the array of vectors.

### Node of segment Tree

Here each leaf node contains a vector which has all the prime factors of a particular A[i] in sorted order.

### Merging of segment nodes

while merging we are just taking the union of 2 sorted vectors.

### Querying the segment tree

In each query first i am finding the segment i.e. l to r which is required by that particular query. Now after i have found such a segment i.e. now i have vector that contains the prime factors of all the numbers in the range l to r of A[i]. Now i just need to find x and y in this vector as the difference of their index will give me the count of prime divisors for that query.

### ALTERNATIVE SOLUTION:

Please share any other approach which is better then mine or suggest any improvements in my current approach.

### EDITORIALIST’S SOLUTIONS:

Can be found here.