My approach was simple just to sieve out all numbers 2 to 10^6 and keeping the lowest prime factor ,then I can get the sum of powers of primes in range **X** and **Y** for that particular number.

my code was: https://www.codechef.com/viewsolution/14162128

but it runs in **O(Q N(logN))** getting only 30 points. I tried to solve it using segment tree but seeing 4 variables (2 different ranges namely

**X**to

**Y**and

**L**to

**R**) I skipped that.Help! Plz.