human
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"
How can the above be solved in Python?
 Write me a code to split the given string into Primes : Digit DP and the other steps required?
assistant
#Here is code to split the given string into Primes : Digit DP and the other steps required.
 def getPrimesFromSeive ( primes ) :
	prime = [ True ] * ( 1000001 )
	prime [ 0 ] , prime [ 1 ] = False , False
	i = 2
	while ( i * i <= 1000000 ) :
		if ( prime [ i ] == True ) :
			for j in range ( i * i , 1000001 , i ) :
				prime [ j ] = False
		i += 1
	for i in range ( 2 , 1000001 ) :
		if ( prime [ i ] == True ) :
			primes . append ( str ( i ) )
def splitIntoPrimes ( number ) :
	numLen = len ( number )
	splitDP = [ - 1 ] * ( numLen + 1 )
	primes = [ ]
	getPrimesFromSeive ( primes )
	for i in range ( 1 , numLen + 1 ) :
		if ( i <= 6 and ( number [ 0 : i ] in primes ) ) :
			splitDP [ i ] = 1
		if ( splitDP [ i ] != - 1 ) :
			j = 1
			while ( j <= 6 and ( i + j <= numLen ) ) :
				if ( number [ i : i + j ] in primes ) :
					if ( splitDP [ i + j ] == - 1 ) :
						splitDP [ i + j ] = 1 + splitDP [ i ]
					else :
						splitDP [ i + j ] = min ( splitDP [ i + j ] , 1 + splitDP [ i ] )
				j += 1
	return splitDP [ numLen ]
print ( splitIntoPrimes ( "13499315" ) )
print ( splitIntoPrimes ( "43" ) )