Find all possible ways to Split the given string into Primes | Javascript 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
let primes = new Array ( 1000000 ) ; const maxn = 1000000 ; function sieve ( ) { primes . fill ( true ) primes [ 0 ] = primes [ 1 ] = 0 ; for ( let i = 2 ; i * i <= maxn ; i ++ ) { if ( primes [ i ] ) { for ( let j = i * i ; j <= maxn ; j += i ) primes [ j ] = false ; } } } function toBinary ( n ) { let r = " " ; while ( n != 0 ) { r = ( n % 2 == 0 ? " " : " " ) + r ; n = Math . floor ( n / 2 ) ; } return ( r == " " ) ? " " : r ; } function PrimeSplit ( str ) { let temp ; let cnt = 0 ; let ans = new Array ( ) ; let bt = 1 << ( str . length - 1 ) ; let n = str . length ; for ( let i = 0 ; i < bt ; i ++ ) { temp = toBinary ( i ) + " " ; let j = 0 , x = n - temp . length , y ; while ( j < x ) { temp = " " + temp ; j ++ ; } j = 0 ; x = 0 ; y = - 1 ; let sp = " " , tp = " " ; let flag = 0 ; while ( j < n ) { sp += str [ j ] ; if ( temp [ j ] == ' ' ) { tp += sp + ' ' ; y = parseInt ( sp ) ; if ( ! primes [ y ] ) { flag = 1 ; break ; } sp = " " ; } j ++ ; } tp += sp ; if ( sp != " " ) { y = parseInt ( sp ) ; if ( ! primes [ y ] ) flag = 1 ; } if ( ! flag ) ans . push ( tp ) ; } if ( ans . length == 0 ) { document . write ( - 1 + " " ) ; } for ( let i of ans ) { document . write ( i + " " ) ; } } let str = " " ; sieve ( ) ; PrimeSplit ( str ) ;