Count N |  ; Stores the dp states ; Check if a number is a prime or not ; Function to generate all prime numbers that are less than or equal to n ; Base cases . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of as non - prime ; Function to find the count of N - digit numbers such that the sum of digits is a prime number ; If end of array is reached ; If the sum is equal to a prime number ; Otherwise ; If the dp - states are already computed ; If index = 1 , any digit from [ 1 - 9 ] can be placed . If N = 1 , 0 also can be placed . ; Otherwise , any digit from [ 0 - 9 ] can be placed . ; Return the answer . ; Driver Code ; Initializing dp array with - 1 ; Initializing prime array to true ; Find all primes less than or equal to 1000 , which is sufficient for N upto 100 ; Given Input ; Function call
import java . util . Arrays ; class GFG { public static int [ ] [ ] dp = new int [ 100 ] [ 1000 ] ; public static boolean [ ] prime = new boolean [ 1005 ] ; public static void SieveOfEratosthenes ( int n ) { prime [ 0 ] = prime [ 1 ] = false ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } } public static int countOfNumbers ( int index , int sum , int N ) { if ( index == N + 1 ) { if ( prime [ sum ] == true ) { return 1 ; } return 0 ; } int val = dp [ index ] [ sum ] ; if ( val != - 1 ) { return val ; } val = 0 ; if ( index == 1 ) { for ( int digit = ( N == 1 ? 0 : 1 ) ; digit <= 9 ; ++ digit ) { val += countOfNumbers ( index + 1 , sum + digit , N ) ; } } else { for ( int digit = 0 ; digit <= 9 ; ++ digit ) { val += countOfNumbers ( index + 1 , sum + digit , N ) ; } } return val ; } public static void main ( String args [ ] ) { for ( int [ ] row : dp ) Arrays . fill ( row , - 1 ) ; Arrays . fill ( prime , true ) ; SieveOfEratosthenes ( 1000 ) ; int N = 6 ; System . out . println ( countOfNumbers ( 1 , 0 , N ) ) ; } }