### PROBLEM LINK:

**Author:** Vipul Sharma

**Tester:** Prateek Gupta

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Segment tree

### PROBLEM:

You are given array of n integers and q queries. For each query you have to sum up number of times prime numbers from [x;y] occur in elements of a from [l;r].

### EXPLANATION:

Any number C consists of at most O(\log C) distinct prime divisors. We can keep all this divisors in segment tree and ask queries of kind how many numbers are there on segment [l;r] such that x \leq a[i] \leq y. We have total of O(n \log C) numbers in segment tree. Now we can answer those queries in O((\log{(n \log C)})^2) per query with if we keep in each vertex of segment tree sorted array of numbers which occur on its segment.

We can answer a query in \mathcal{O}(\log{(n \log C)}) time by using persistent segment tree. For each prime x from 2 to max(A_i), we will maintain a version of segment tree, which the version y can tell the answer for query (1, y) for some given [l, r]. We can maintain these versions of the segment trees using persistent segment tree. The answer for query [x, y] and [l, r] will be answer of query [l, r] in y-th version of the segment tree subtracted by answer of the query [l, r] in the (x-1)^{th} version of segment tree.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution

Tester’s solution