Find all possible ways to Split the given string into Primes | Java 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
import java . util . * ; import java . lang . * ; class GFG { static boolean [ ] primes = new boolean [ 1000001 ] ; static int maxn = 1000000 ; static void sieve ( ) { Arrays . fill ( primes , true ) ; primes [ 0 ] = false ; primes [ 1 ] = false ; for ( int i = 2 ; i * i <= maxn ; i ++ ) { if ( primes [ i ] ) { for ( int j = i * i ; j <= maxn ; j += i ) primes [ j ] = false ; } } } static String toBinary ( int n ) { String r = " " ; while ( n != 0 ) { r = ( n % 2 == 0 ? "0" : "1" ) + r ; n /= 2 ; } return ( r == " " ) ? "0" : r ; } static void PrimeSplit ( String str ) { String temp ; int cnt = 0 ; ArrayList < String > ans = new ArrayList < > ( ) ; int bt = 1 << ( str . length ( ) - 1 ) ; int n = str . length ( ) ; for ( int i = 0 ; i < bt ; i ++ ) { temp = toBinary ( i ) + "0" ; int j = 0 , x = n - temp . length ( ) , y ; while ( j < x ) { temp = "0" + temp ; j ++ ; } j = 0 ; x = 0 ; y = - 1 ; String sp = " " , tp = " " ; boolean flag = false ; while ( j < n ) { sp += str . charAt ( j ) ; if ( temp . charAt ( j ) == '1' ) { tp += sp + ' , ' ; y = Integer . parseInt ( sp ) ; if ( ! primes [ y ] ) { flag = true ; break ; } sp = " " ; } j ++ ; } tp += sp ; if ( sp != " " ) { y = Integer . parseInt ( sp ) ; if ( ! primes [ y ] ) flag = true ; } if ( ! flag ) ans . add ( tp ) ; } if ( ans . size ( ) == 0 ) { System . out . println ( - 1 ) ; } for ( String i : ans ) { System . out . println ( i ) ; } } public static void main ( String [ ] args ) { String str = "11373" ; sieve ( ) ; PrimeSplit ( str ) ; } }