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?