Counting primes- Codechef

#1

Its giving time limit error for 3 rd subtask which is
1 ≤ T ≤ 105
1 ≤ M ≤ 107
1 ≤ N ≤ 107
I have used all the 3 optimisations, its exceeding the time limit of 2 seconds(2.01s)
can u pls check where am i wrong


question link - https://www.codechef.com/problems/CNTPRIME

#2

hey @sktg99, changed few things in the code : https://ide.codingblocks.com/s/131135

#3

okay its correct, but how did u know that this code would give more optimised answer?

#4

consider the worst case:
value of T = 10^5
and for each case a = 1 and b = 10^7
you are recomputing results again and again… the best way to optimize this problem is to store the result you already computed, so that’s what i have done.

#5

oh yes thanks!!!