Queries to count Palindrome Numbers from a range whose sum of digits is a Prime Number | Java 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
class GFG { static int [ ] arr = new int [ 100005 ] ; static boolean 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 ; } } static int sumOfDigits ( int N ) { int sum = 0 ; while ( N != 0 ) { sum += N % 10 ; N /= 10 ; } return sum ; } static boolean isPrime ( int n ) { if ( n <= 1 ) { return false ; } for ( int i = 2 ; i <= n / 2 ; ++ i ) { if ( n % i == 0 ) return false ; } return true ; } static 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 ] ; } } static void countNumbers ( int [ ] [ ] Q , int N ) { precompute ( ) ; for ( int i = 0 ; i < N ; i ++ ) { System . out . println ( ( arr [ Q [ i ] [ 1 ] ] - arr [ Q [ i ] [ 0 ] - 1 ] ) ) ; } } public static void main ( String [ ] args ) { int [ ] [ ] Q = { { 5 , 9 } , { 1 , 101 } } ; int N = Q . length ; countNumbers ( Q , N ) ; } }