Split the given string into Primes : Digit DP | Function to precompute all the primes upto 1000000 and store it in a set using Sieve of Eratosthenes ; Here str ( ) is used for converting int to string ; A function to find the minimum number of segments the given string can be divided such that every segment is a prime ; Declare a splitdp [ ] array and initialize to - 1 ; Call sieve function to store primes in primes array ; Build the DP table in a bottom - up manner ; If the prefix is prime then the prefix will be found in the prime set ; If the Given Prefix can be split into Primes then for the remaining string from i to j Check if Prime . If yes calculate the minimum split till j ; To check if the substring from i to j is a prime number or not ; If it is a prime , then update the dp array ; Return the minimum number of splits for the entire string ; Driver code
def getPrimesFromSeive ( primes ) : NEW_LINE INDENT prime = [ True ] * ( 1000001 ) NEW_LINE prime [ 0 ] , prime [ 1 ] = False , False NEW_LINE i = 2 NEW_LINE while ( i * i <= 1000000 ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT for j in range ( i * i , 1000001 , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT for i in range ( 2 , 1000001 ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT primes . append ( str ( i ) ) NEW_LINE DEDENT DEDENT DEDENT def splitIntoPrimes ( number ) : NEW_LINE INDENT numLen = len ( number ) NEW_LINE splitDP = [ - 1 ] * ( numLen + 1 ) NEW_LINE primes = [ ] NEW_LINE getPrimesFromSeive ( primes ) NEW_LINE for i in range ( 1 , numLen + 1 ) : NEW_LINE INDENT if ( i <= 6 and ( number [ 0 : i ] in primes ) ) : NEW_LINE INDENT splitDP [ i ] = 1 NEW_LINE DEDENT if ( splitDP [ i ] != - 1 ) : NEW_LINE INDENT j = 1 NEW_LINE while ( j <= 6 and ( i + j <= numLen ) ) : NEW_LINE INDENT if ( number [ i : i + j ] in primes ) : NEW_LINE INDENT if ( splitDP [ i + j ] == - 1 ) : NEW_LINE INDENT splitDP [ i + j ] = 1 + splitDP [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT splitDP [ i + j ] = min ( splitDP [ i + j ] , 1 + splitDP [ i ] ) NEW_LINE DEDENT DEDENT j += 1 NEW_LINE DEDENT DEDENT DEDENT return splitDP [ numLen ] NEW_LINE DEDENT print ( splitIntoPrimes ( "13499315" ) ) NEW_LINE print ( splitIntoPrimes ( "43" ) ) NEW_LINE