Count of ways to split a given number into prime segments | Python3 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
MOD = 1000000007 NEW_LINE sieve = [ 0 ] * ( 1000000 ) NEW_LINE def buildSieve ( ) : NEW_LINE INDENT for i in range ( len ( sieve ) ) : NEW_LINE INDENT sieve [ i ] = True NEW_LINE DEDENT sieve [ 0 ] = False NEW_LINE sieve [ 1 ] = False NEW_LINE p = 2 NEW_LINE while p * p <= 1000000 : NEW_LINE INDENT if sieve [ p ] == True : NEW_LINE INDENT for i in range ( p * p , 1000000 , p ) : NEW_LINE INDENT sieve [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def isPrime ( number ) : NEW_LINE INDENT num = int ( number ) NEW_LINE return sieve [ num ] NEW_LINE DEDENT def rec ( number , i , dp ) : NEW_LINE INDENT if dp [ i ] != - 1 : NEW_LINE INDENT return dp [ i ] NEW_LINE DEDENT cnt = 0 NEW_LINE for j in range ( 1 , 7 ) : NEW_LINE if ( i - j ) >= 0 and number [ i - j ] != '0' and isPrime ( number [ i - j : i ] ) : NEW_LINE INDENT cnt += rec ( number , i - j , dp ) NEW_LINE cnt %= MOD NEW_LINE DEDENT dp [ i ] = cnt NEW_LINE return dp [ i ] NEW_LINE DEDENT def countPrimeStrings ( number ) : NEW_LINE INDENT n = len ( number ) NEW_LINE dp = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] = - 1 NEW_LINE DEDENT dp [ 0 ] = 1 NEW_LINE return rec ( number , n , dp ) NEW_LINE DEDENT buildSieve ( ) NEW_LINE s1 = "3175" NEW_LINE print ( countPrimeStrings ( s1 ) ) NEW_LINE