# Count of ways to split a given number into prime segments
###### tags: `Dynamic Programming`, `Amazon OA`

Description:
Given numeric string `str`, the task is to count the number of ways the given string can be split, such that each segment is a **prime number**. Since the answer can be large, *return the answer modulo `10^9 + 7`*.

Note: A split that contains numbers with **leading zeroes will be invalid** and the initial string does not contain leading zeroes.

Solution:

public class CountPrimeStrings {
    public int CountPrimeString(String str) {
        int n = str.length();
        boolean[] sieve = buildSieve();
        // dp[i]: # of ways to split substring(0, i) into primes 
        long[] dp = new long[n + 1];
        int mod = 1000000000 + 7;
        dp[0] = 1L;

        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                String sub = str.substring(j, i);
                if (sub.startsWith("0")) continue;
                int num = Integer.parseInt(sub);
                if (sieve[num]) dp[i] += dp[j];
                dp[i] %= mod;
            }
        }
        return (int)dp[n];
    }

    private boolean[] buildSieve() {
        boolean[] sieve = new boolean[1000001];
        sieve[0] = false;
        sieve[1] = false;
        for (int i = 0; i < sieve.length; i++) {
            sieve[i] = isPrime(i);
        }
        return sieve;
    }

    private boolean isPrime(int num) {
        if (num == 1) return false;
        int i = 2;
        while (i * i <= num) {
            if (num % i == 0) {
                return false;
            }
            i++;
        }
        return true;
    }
}