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]].
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.