Why i am getting tle

#1

i am using segmenented sieve then also getting tle,pl look into it.
My code:https://ide.codingblocks.com/s/207719

#2

@spagire4 Here https://ide.codingblocks.com/s/207744 I optimised your code please see.

#3

Sir can u pl elaborate ur optimization ::

#4

@sdevwrat sir i am unable to figure out what u have done

#5

See line 25 to 37 in your code, it runs in sqrt(b)*(b-a) time which is way too much when you have these many testcases, so I optimised this part, first by deciding where I should start from, i.e. finding the closest multiple to a for any i if i is less than a or just start from i if i>a. Then we know that if we find some multiple y for any i, then the next multiple will lie at y+i, so i just skipped all the parts in-between and made this my update statement. This logic is similar to one used in sieve and helps bring down the time complexity.