Split the given string into Primes : Digit DP | 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
def checkPrime ( number ) : NEW_LINE INDENT num = int ( number ) NEW_LINE for i in range ( 2 , int ( num ** 0.5 ) ) : NEW_LINE INDENT if ( ( num % i ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def splitIntoPrimes ( number ) : NEW_LINE INDENT if ( number == ' ' ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( len ( number ) <= 6 and checkPrime ( number ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT numLen = len ( number ) NEW_LINE ans = 1000000 NEW_LINE for i in range ( 1 , ( min ( 6 , numLen ) + 1 ) ) : NEW_LINE INDENT if ( checkPrime ( number [ : i ] ) ) : NEW_LINE INDENT val = splitIntoPrimes ( number [ i : ] ) NEW_LINE if ( val != - 1 ) : NEW_LINE INDENT ans = min ( ans , 1 + val ) NEW_LINE DEDENT DEDENT DEDENT if ( ans == 1000000 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT DEDENT print ( splitIntoPrimes ( "13499315" ) ) NEW_LINE print ( splitIntoPrimes ( "43" ) ) NEW_LINE