Split the given string into Primes : Digit DP | Java implementation of the above approach ; Function to check whether a String is a prime number or not ; A recursive function to find the minimum number of segments the given String can be divided such that every segment is a prime ; If the number is null ; checkPrime function is called to check if the number is a prime or not . ; A very large number denoting maximum ; Consider a minimum of 6 and length since the primes are less than 10 ^ 6 ; Recursively call the function to check for the remaining String ; Evaluating minimum splits into Primes for the suffix ; Checks if no combination found ; Driver code
import java . util . * ; class GFG { static boolean checkPrime ( String number ) { int num = Integer . valueOf ( number ) ; for ( int i = 2 ; i * i <= num ; i ++ ) if ( ( num % i ) == 0 ) return false ; return true ; } static int splitIntoPrimes ( String number ) { if ( number . length ( ) == 0 ) return 0 ; if ( number . length ( ) <= 6 && checkPrime ( number ) ) return 1 ; else { int numLen = number . length ( ) ; int ans = 1000000 ; for ( int i = 1 ; i <= 6 && i <= numLen ; i ++ ) { if ( checkPrime ( number . substring ( 0 , i ) ) ) { int val = splitIntoPrimes ( number . substring ( i ) ) ; if ( val != - 1 ) { ans = Math . min ( ans , 1 + val ) ; } } } if ( ans == 1000000 ) return - 1 ; return ans ; } } public static void main ( String [ ] args ) { System . out . print ( splitIntoPrimes ( "13499315" ) + "NEW_LINE"); System . out . print ( splitIntoPrimes ( "43" ) + "NEW_LINE"); } }