text: Queries to count Palindrome Numbers from a range whose sum of digits is a Prime Number | C ++ program for the above approach ; Function to check if the number N is palindrome or not ; Store the value of N ; Store the reverse of number N ; Reverse temp and store in res ; If N is the same as res , then return true ; Function to find the sum of the digits of the number N ; Stores the sum of the digits ; Add the last digit of the number N to the sum ; Remove the last digit from N ; Return the resultant sum ; Function to check if N is prime or not ; If i is 1 or 0 , then return false ; Check if i is divisible by any number in the range [ 2 , n / 2 ] ; If n is divisible by i ; Function to precompute all the numbers till 10 ^ 5 that are palindromic and whose sum of digits is prime numbers ; Iterate over the range 1 to 10 ^ 5 ; If i is a palindrome number ; Stores the sum of the digits in i ; If the sum of digits in i is a prime number ; Find the prefix sum of arr [ ] ; Function to count all the numbers in the given ranges that are palindromic and the sum of digits is prime numbers ; Function Call to precompute all the numbers till 10 ^ 5 ; Traverse the given queries Q [ ] ; Print the result for each query ; Driver Code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int arr [ 100005 ] ; bool isPalindrome ( int N ) { int temp = N ; int res = 0 ; while ( temp != 0 ) { int rem = temp % 10 ; res = res * 10 + rem ; temp /= 10 ; } if ( res == N ) { return true ; } else { return false ; } } int sumOfDigits ( int N ) { int sum = 0 ; while ( N != 0 ) { sum += N % 10 ; N /= 10 ; } return sum ; } bool isPrime ( int n ) { if ( n <= 1 ) { return false ; } for ( int i = 2 ; i <= n / 2 ; ++ i ) { if ( n % i == 0 ) return false ; } return true ; } void precompute ( ) { for ( int i = 1 ; i <= 100000 ; i ++ ) { if ( isPalindrome ( i ) ) { int sum = sumOfDigits ( i ) ; if ( isPrime ( sum ) ) arr [ i ] = 1 ; else arr [ i ] = 0 ; } else arr [ i ] = 0 ; } for ( int i = 1 ; i <= 100000 ; i ++ ) { arr [ i ] = arr [ i ] + arr [ i - 1 ] ; } } void countNumbers ( int Q [ ] [ 2 ] , int N ) { precompute ( ) ; for ( int i = 0 ; i < N ; i ++ ) { cout << ( arr [ Q [ i ] [ 1 ] ] - arr [ Q [ i ] [ 0 ] - 1 ] ) ; cout << endl ; } } int main ( ) { int Q [ ] [ 2 ] = { { 5 , 9 } , { 1 , 101 } } ; int N = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ; countNumbers ( Q , N ) ; }