Skip to main content

Posts

Showing posts with the label sieve

Solving CodeChef June Long Challenge Problem "PRMQ" using Segment Tree

Hello folks. Hope you are having a good time. I wanted to share my solution to CodeChef June '17 problem   PRMQ . Though there might be many solutions possible to this problem, I will walk you through a Segment-Tree solution for this. Approach There are nearly 78,000 prime numbers between 1 and 10^6, so in worst case a number in this query range L to R can have maximum of 8 prime numbers as the number of factors. Why 8 see 2*3*5*7*11*13*17*19 > 10^6 . And the root node can have maximum of 78,000 nodes with each prime number in the leaf node merging to form the root node. Now let us think what we should store in a node of segment tree. We may need the following information:- 1. The element of the array so as to compute their prime factors. 2. Some way to combine the factors of each element as key and their count as value, suppose we are having 2 elements say 8 and 9 so when we merge these node in the tree, we have got 2 as a factor with count 3 and 3 as a factor with