Count of ways to split a given number into prime segments | C # 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
using System ; class GFG { static int MOD = 1000000007 ; static bool [ ] sieve = new bool [ 1000000 ] ; static void buildSieve ( ) { for ( int j = 0 ; j < sieve . Length ; j ++ ) sieve [ j ] = 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 bool isPrime ( String number ) { int num = Int32 . Parse ( 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 [ i - j ] != '0' && isPrime ( number . Substring ( i - j , j ) ) ) { 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 ] ; for ( int j = 0 ; j < dp . Length ; j ++ ) dp [ j ] = - 1 ; dp [ 0 ] = 1 ; return rec ( number , n , dp ) ; } public static void Main ( String [ ] args ) { buildSieve ( ) ; String s1 = "3175" ; Console . Write ( countPrimeStrings ( s1 ) + " STRNEWLINE " ) ; } }