Very nice work, simplicity at its best. Thanks for this editorial . Hope you will put up more like this :)

How about this solution

I think everyone is familiar with the brute force solution :

We create a 2D array count of size 100000*78498 and for each arr[i] for (1 <= i <= n) we store the number of times the jth prime number divides it. Then for each j we can calculate contiguous sum for 1 to n and store it in a new array conti_count as shown below.

for(int i = 1; i <= n; i++) { for(int j = 0; j < p.size(); j++) conti_count[i][j] = conti_count[i-1][j] + count[i][j]; }

But now the problem is size of 2D array and complexity of the above code spinet. Can we do something better ?

Alright answer this : How many prime divisor of a number n exists at max which are greater than sqrt(n).

The answer is : 1, because if you divide n with m ( where m >= sqrt(n) ) the result is less than sqrt(n).

Using the above fact we can reduce the code complexity from O(100000*78498) to O(100000*168)` for the pre calculation part. So now what different are we doing from our initial brute force solution ?

We are calculating the above mentioned count only for the prime numbers less than 1000. Now for each query we can iterate from index[max(1,x)] to index[min(1000,y)] and count number of appearance of all prime numbers between 1 to 1000 in range l to r, where index stores the rank of prime number (max value is 168).

What is left is to handle case of calculating number of integers in range l to r with a prime factor greater than max(1000,x) to y. So while doing prime factorisation of each number during precomputation we make an array and for each i in range 1 to n and we store the prime factor of arr[i] which is greater than 1000. Now we can either use trie or merge sort tree to compute number of integers less than equal to y in range l to r and number of integers less than x in range l to r in log(n) each.

You can view my solution for better understanding : PRMQ

I applied the same approach, but instead of using vector i used map to keep record of prime divisors and their corresponding powers. First i used segment tree but only scored 10 marks. you can check my solution here. but after it i used fenwick tree for optimization but still scored only 30 marks. could anyone suggest me what's wrong in my solutions. here is my solution.

Very good and simple to understand approach! Great Job!

I used persistent segment tree. https://www.codechef.com/viewsolution/14223288

Hi @d4dev . Thanks Because of you i learnt segment trees for the first time. Can you once explain me the query part if you don't mind. Thanks.

Hi @d4dev, your solution is very well explained without increasing the complexity of any operation. I applied the same approach but was able to score points only for Subtask 1 & 2 only and I was getting WA for all the testcases in the last subtask. Could you have a look at my code and telling me what am I doing wrong. Here is My Code.

Thanks

can anyone tell if why my solution is not working....here

In a node,i have stored vector of pair where first is prime factor and second is the power.

struct node{
    vector<pair<int,int> >pr;
    int size;
};

i have submitted it around 35 times but no luck.Please help me.

@d4dev I tried to do this question as told by you. But I am stuck on this for long. I am getting only 20 points. Tried all things but not getting an AC. Can someone please help me with this. @d4dev my solution is similar to yours ,it won't take much time.

Please Help. Thanks. Link to my solution https://www.codechef.com/viewsolution/14641252

@vijju123,@siddhartp538 Thank you so much for pointing this out. I was struggling with it a lot. Actually, the mistake was :

I was trying to maintain an array sieve[] which keeps the smallest prime factor. In this way any number, prime factors can be found in O(logN) (after sieve). But while applying the sieve, By mistake i was keeping the highest prime factor (overwriting everytime as soon as it get a prime factor).

In simple words say 40. Now this no. has smallest prime factor 2 which i intended to store in sieve[40]. But when loop reaches to 5 sieve[40] was changed to 5. The only change i need to do was if(sieve[j]==0) sieve[j]=i; where i is the first and j is the second loop in sieve function. So now only those which are 0 are changed. And there will be no overwriting of prime factors.

And if smallest prime factor is stored you automatically get sorted prime factors of any no. in logN.

Thank you again :) Finally an AC.