### PROBLEM LINK:

**Author:** Suraj Kumar

**Tester:** Rishabh Gupta

**Editorialist:** Suraj Kumar

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Data Structure, Segment tree, Sieve of Eratothenes

### PROBLEM:

You are given an array of N inegers on which you have to perform

Q queries which can be of update type in which you need to change

the content at index i with X.

The other type of query is to count the total number of primes

between a given range of indices L and R.

### QUICK EXPLANATION:

Find an efficient way to tell the no. of prime numbers between

two given indices of an Array.

### EXPLANATION:

The problem is pretty straightforward.

First of all we need to find all the prime numbers from 1 to

100000, which can be done using the sieve.

After this is done we need to build the segment tree, which

can be done in order of nlogn.

After the tree is built we simply need to query the tree for

each of the query of first type in order of logn.

For the update query we need to change only those part of the

tree which will be affected by this update. This can also be

done in logn.

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

Author’s solution can be found here.

Tester’s solution can be found here.