for the question CodeChef: Practical coding for everyone
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 ( CodeChef: Practical coding for everyone ) and tell what in my code makes it go beyond time limit?
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}.
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.