Why my code for JMAGNUM gives TLE

for the question https://www.codechef.com/LOCSEP17/problems/JMAGNUM
Though I didn’t use sieve in my code but I feel I am using lesser numbers of loops.
I made an array of all prime number less than 1000 (168 in number). Then using these prime numbers I made an array of all prime numbers less than 10^6 (total prime number less than 10^6 is 78498). I then made another array which stored the digitsum of all(78498) prime numbers. Then for every test case i moved through the array of prime numbers and calculated the frequency(mult, in program) of ith prime numbers by using equation
mult=(r-l)/p[i] (addition conditions were added for corner cases) and then added the product of mult and the digitsum of p[i] to sum i.e. sum=sum+mult*digitsum[a[i]].

But for the 2nd subtask I got TLE.
Can you check my code ( https://www.codechef.com/viewsolution/15587726 ) and tell what in my code makes it go beyond time limit?

std::ios::sync_with_stdio(false); // add this inside main() function as the first line of main()

This Line Can remove TLE sometimes…

T is upto {10}^{4} . If your algorithm isnt LogN , then more or less its going to fail.

The method using sieve also have the complexity of NLogN I guess. Isn’t it?

Ok I will try this.

But what does it mean?

it’s for fast Input/Output.
But that doesn’t help here as the input file cannot be that large!

Maintain a prefix sum array when prefix[i] will denote sum of magic values of all numbers from 0 to i.
Using this you can answer each test case in O(1).You just need to print prefix[R] - prefix[L - 1}.

Happy Coding !

Ok fine I got it. As the number of test cases is very large it would be better to calculate all those prefix(i) in the beginning itself and then directly using that. Thank you.

yours is n sqrt(n) @rp789 [n being small since you reduced it]