Split the given string into Primes : Digit DP | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void getPrimesFromSeive ( set < string > & primes ) { bool prime [ 1000001 ] ; memset ( prime , true , sizeof ( prime ) ) ; 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 . insert ( to_string ( i ) ) ; } } int splitIntoPrimes ( string number ) { int numLen = number . length ( ) ; int splitDP [ numLen + 1 ] ; memset ( splitDP , -1 , sizeof ( splitDP ) ) ; set < string > primes ; getPrimesFromSeive ( primes ) ; for ( int i = 1 ; i <= numLen ; i ++ ) { if ( i <= 6 && ( primes . find ( number . substr ( 0 , i ) ) != primes . end ( ) ) ) splitDP [ i ] = 1 ; if ( splitDP [ i ] != -1 ) { for ( int j = 1 ; j <= 6 && i + j <= numLen ; j ++ ) { if ( primes . find ( number . substr ( i , j ) ) != primes . end ( ) ) { if ( splitDP [ i + j ] == -1 ) splitDP [ i + j ] = 1 + splitDP [ i ] ; else splitDP [ i + j ] = min ( splitDP [ i + j ] , 1 + splitDP [ i ] ) ; } } } } return splitDP [ numLen ] ; } int main ( ) { cout << splitIntoPrimes ( "13499315" ) << " STRNEWLINE " ; cout << splitIntoPrimes ( "43" ) << " STRNEWLINE " ; return 0 ; }