Count of ways to split a given number into prime segments | Javascript 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
let MOD = 1000000007 ; let sieve = new Array ( 1000000 ) ; function buildSieve ( ) { for ( let i = 0 ; i < sieve . length ; i ++ ) { sieve [ i ] = true ; } sieve [ 0 ] = false ; sieve [ 1 ] = false ; for ( let p = 2 ; p * p <= 1000000 ; p ++ ) { if ( sieve [ p ] == true ) { for ( let i = p * p ; i < 1000000 ; i += p ) sieve [ i ] = false ; } } } function isPrime ( number ) { let num = parseInt ( number ) ; return sieve [ num ] ; } function rec ( number , i , dp ) { if ( dp [ i ] != - 1 ) return dp [ i ] ; let cnt = 0 ; for ( let j = 1 ; j <= 6 ; j ++ ) { if ( i - j >= 0 && number [ i - j ] != ' ' && isPrime ( number . substring ( i - j , i ) ) ) { cnt += rec ( number , i - j , dp ) ; cnt %= MOD ; } } return dp [ i ] = cnt ; } function countPrimeStrings ( number ) { let n = number . length ; let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < ( n + 1 ) ; i ++ ) { dp [ i ] = - 1 ; } dp [ 0 ] = 1 ; return rec ( number , n , dp ) ; } buildSieve ( ) ; let s1 = " " ; document . write ( countPrimeStrings ( s1 ) + " " ) ;