Ok …but mera 1st point ko solve kro…Kya hame sum of digit krna hi padega kya
Sare good no. Less than r right
Yes…for sure… …(20…chars…)
Hame har ek no. Ka sum of digit krne me log10(n) lagnege right
Do this:-
Store every good number less than 10^7 in array ‘b’ .
Size of array ‘b’ will be something around 10^6.
Now, for each query, read l and r. Do binary search for ‘l’ and ‘r’ in array ‘b’ and u get the count of good numbers from 1 to l and 1 to r, say x and y, answer is y-x 
Are bhai jitne digit has, 6 or 7, O(6) lagega per number , zyaada socho mat.
Ha ye to aagya… 20 char
Acchaa…ha vo bhi…
Or agar range 10^18 ho to
17*81 tk prime store karvau…hna
Really…
Then it will be okay 
Yeah but when b-a is small it will be dominant.
So I kept it.
Even then it doesn’t matter as 567.log… is too small 
1 Like
Still I won’t discard it from formal complexity
Step 1: The upper bound for the number is 9999999. Thus, the “maximum possible prime” for sum of squares = 7*81 = 567. Lets calculate all primes from 1 to 567. Store it in a set. Or even better, build a boolean array (568 bits)
Step 2: For i in range: calculate sum of digits, is it in the set (or check if boolean array at index “sum” is 1 or 0? If yes, calculate sum of square of digits, is it in the set? If it is - add it to output vector.
This is an O(n) algorithm - considering that building list of primes till 567 will take trivial time.