Prime visits hacker block

#1


one test case is showing time limit… rest two is passed

#2

hello @chaman9 ,
a) you are getting tle because ur solution time complexity is high roughly O(t*(n-m)* sqrt(n) )

to optimise it .precompute number of primes in range 1 t0 highest value of (n) and then u can answer to each query in O(1)

#3

hey
i am not getting how to reduce time complexity thing

#4

@chaman9
ok leave it, just build sieve . and then iterate from m to n . if number is prime then increment count

#5

okay thanks
i will try

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.