Split the given string into Primes : Digit DP | Java implementation of the above approach ; Function to precompute all the primes upto 1000000 and store it in a set using Sieve of Eratosthenes ; Here to_String ( ) 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
import java . util . * ; class GFG { static void getPrimesFromSeive ( HashSet < String > primes ) { boolean [ ] prime = new boolean [ 1000001 ] ; Arrays . fill ( prime , true ) ; prime [ 0 ] = prime [ 1 ] = false ; for ( int i = 2 ; i * i <= 1000000 ; i ++ ) { if ( prime [ i ] == true ) { for ( int j = i * i ; j <= 1000000 ; j += i ) prime [ j ] = false ; } } for ( int i = 2 ; i <= 1000000 ; i ++ ) { if ( prime [ i ] == true ) primes . add ( String . valueOf ( i ) ) ; } } static int splitIntoPrimes ( String number ) { int numLen = number . length ( ) ; int [ ] splitDP = new int [ numLen + 1 ] ; Arrays . fill ( splitDP , - 1 ) ; HashSet < String > primes = new HashSet < String > ( ) ; getPrimesFromSeive ( primes ) ; for ( int i = 1 ; i <= numLen ; i ++ ) { if ( i <= 6 && ( primes . contains ( number . substring ( 0 , i ) ) ) ) splitDP [ i ] = 1 ; if ( splitDP [ i ] != - 1 ) { for ( int j = 1 ; j <= 6 && i + j <= numLen ; j ++ ) { if ( primes . contains ( number . substring ( i , i + j ) ) ) { if ( splitDP [ i + j ] == - 1 ) splitDP [ i + j ] = 1 + splitDP [ i ] ; else splitDP [ i + j ] = Math . min ( splitDP [ i + j ] , 1 + splitDP [ i ] ) ; } } } } return splitDP [ numLen ] ; } public static void main ( String [ ] args ) { System . out . print ( splitIntoPrimes ( "13499315" ) + "NEW_LINE"); System . out . print ( splitIntoPrimes ( "43" ) + "NEW_LINE"); } }