Find all possible ways to Split the given string into Primes | Python 3 program to Find all the ways to split the given string into Primes . ; Sieve of Eratosthenes ; Function Convert integer to binary string ; Function print all the all the ways to split the given string into Primes . ; To store all possible strings ; Exponetnital complexity n * ( 2 ^ ( n - 1 ) ) for bit ; Pruning step ; Driver code
primes = [ True ] * 1000001 NEW_LINE maxn = 1000000 NEW_LINE def sieve ( ) : NEW_LINE INDENT primes [ 0 ] = primes [ 1 ] = 0 NEW_LINE i = 2 NEW_LINE while i * i <= maxn : NEW_LINE INDENT if ( primes [ i ] ) : NEW_LINE INDENT for j in range ( i * i , maxn + 1 , i ) : NEW_LINE INDENT primes [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def toBinary ( n ) : NEW_LINE INDENT r = " " NEW_LINE while ( n != 0 ) : NEW_LINE INDENT if ( n % 2 == 0 ) : NEW_LINE r = "0" + r NEW_LINE else : NEW_LINE r = "1" + r NEW_LINE n //= 2 NEW_LINE DEDENT if ( r == " " ) : NEW_LINE return "0" NEW_LINE return r NEW_LINE DEDENT def PrimeSplit ( st ) : NEW_LINE INDENT cnt = 0 NEW_LINE ans = [ ] NEW_LINE bt = 1 << ( len ( st ) - 1 ) NEW_LINE n = len ( st ) NEW_LINE for i in range ( bt ) : NEW_LINE INDENT temp = toBinary ( i ) + "0" NEW_LINE j = 0 NEW_LINE x = n - len ( temp ) NEW_LINE while ( j < x ) : NEW_LINE INDENT temp = "0" + temp NEW_LINE j += 1 NEW_LINE DEDENT j = 0 NEW_LINE x = 0 NEW_LINE y = - 1 NEW_LINE sp = " " NEW_LINE tp = " " NEW_LINE flag = 0 NEW_LINE while ( j < n ) : NEW_LINE INDENT sp += st [ j ] NEW_LINE if ( temp [ j ] == '1' ) : NEW_LINE INDENT tp += sp + ' , ' NEW_LINE y = int ( sp ) NEW_LINE if ( not primes [ y ] ) : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT sp = " " NEW_LINE DEDENT j += 1 NEW_LINE DEDENT tp += sp NEW_LINE if ( sp != " " ) : NEW_LINE INDENT y = int ( sp ) NEW_LINE if ( not primes [ y ] ) : NEW_LINE flag = 1 NEW_LINE DEDENT if ( not flag ) : NEW_LINE ans . append ( tp ) NEW_LINE DEDENT if ( len ( ans ) == 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT for i in ans : NEW_LINE INDENT print ( i ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = "11373" NEW_LINE sieve ( ) NEW_LINE PrimeSplit ( st ) NEW_LINE DEDENT