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 check whether a number is a prime number or not ; Function to find the count of ways to split string into prime numbers ; 1 based indexing ; Consider every suffix up to 6 digits ; Number should not have a leading zero and it should be a prime number ; Return the final result ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MOD  1000000007 NEW_LINE bool isPrime ( string number ) { int num = stoi ( number ) ; for ( int i = 2 ; i * i <= num ; i ++ ) if ( ( num % i ) == 0 ) return false ; return num > 1 ? true : false ; } int countPrimeStrings ( string & number , int i ) { if ( i == 0 ) return 1 ; int cnt = 0 ; for ( int j = 1 ; j <= 6 ; j ++ ) { if ( i - j >= 0 && number [ i - j ] != '0' && isPrime ( number . substr ( i - j , j ) ) ) { cnt += countPrimeStrings ( number , i - j ) ; cnt %= MOD ; } } return cnt ; } int main ( ) { string s1 = "3175" ; int l = s1 . length ( ) ; cout << countPrimeStrings ( s1 , l ) ; return 0 ; }