Count of ways to split a given number into prime segments | Java implementation to count total number of ways to split a String to get prime numbers ; Function to build sieve ; If p is a prime ; Update all multiples of p as non prime ; Function to check whether a number is a prime number or not ; Function to find the count of ways to split String into prime numbers ; Number should not have a leading zero and it should be a prime number ; Function to count the number of prime Strings ; Driver code
import java . util . * ; class GFG { static int MOD = 1000000007 ; static boolean [ ] sieve = new boolean [ 1000000 ] ; static void buildSieve ( ) { Arrays . fill ( sieve , true ) ; sieve [ 0 ] = false ; sieve [ 1 ] = false ; for ( int p = 2 ; p * p <= 1000000 ; p ++ ) { if ( sieve [ p ] == true ) { for ( int i = p * p ; i < 1000000 ; i += p ) sieve [ i ] = false ; } } } static boolean isPrime ( String number ) { int num = Integer . valueOf ( number ) ; return sieve [ num ] ; } static int rec ( String number , int i , int [ ] dp ) { if ( dp [ i ] != - 1 ) return dp [ i ] ; int cnt = 0 ; for ( int j = 1 ; j <= 6 ; j ++ ) { if ( i - j >= 0 && number . charAt ( i - j ) != '0' && isPrime ( number . substring ( i - j , i ) ) ) { cnt += rec ( number , i - j , dp ) ; cnt %= MOD ; } } return dp [ i ] = cnt ; } static int countPrimeStrings ( String number ) { int n = number . length ( ) ; int [ ] dp = new int [ n + 1 ] ; Arrays . fill ( dp , - 1 ) ; dp [ 0 ] = 1 ; return rec ( number , n , dp ) ; } public static void main ( String [ ] args ) { buildSieve ( ) ; String s1 = "3175" ; System . out . print ( countPrimeStrings ( s1 ) + "NEW_LINE"); } }