Split the Number String into Primes in Java

A string is given that is made only of digits, such that the string represents a number. Our task is to split the number string in such a way that each segment of the number that is formed after the split is a prime number. Also, we have to take care to minimize the number of splits. Note that if the input string itself represents a prime number, then the minimum split is 1 as we are taking it as a whole. The prime numbers found have to be in the range of 1 to 10 ^ 6. Let's understand it with the help of a few examples.

Example 1:

Input: "13477317"

Output: 2

Explanation: If we take 1 split, then we have to take 13477317 as a whole, and the number 13477317 is divisible by 3. Hence, 1 split is not possible. Now, we take 2 splits, and we see that 13477 is a prime number and 317 is also a prime number. Thus, in 2 splits, we got all the segments as prime numbers.

Example 2:

Input: "17"

Output: 1

Explanation: If we take 1 split, then we have to take 17 as a whole, and the number 13477317 is a prime number. Hence, 1 split will suffice.

Let's see different approaches to find the splits.

Using Recursion

The concept is to take into consideration each prefix up to 6 digits (as it is already known that the prime numbers are < 10 ^ 6) and validate whether it is a prime number or not. If it is a prime number, then recursively invoke the method to validate the string that is remaining. If any of the combinations do not give the appropriate arrangement, then an appropriate message is shown on the console.

FileName: SplitStringPrimes.java

Output:

For the number 343, the minimum number of splits is: 2 For the number 37, the minimum number of splits is: 1 For the number 44, the minimum number of splits is not possible. For the number 367555, the minimum number of splits is: 4 

Complexity Analysis

The time complexity of the above program is O(N^{5 / 2}), where O(N²) time is taken to recursively find all the possible combinations. As we also have to check whether the number is prime or not, and this task takes the time complexity of O(N^{1 / 2}). Thus, the total time complexity of the above program is O(N²) * O(N^{1 / 2}) = O(N^{5 / 2}), where N is the total number of digits present in the input string.

Using Iteration

Using iteration, one can solve the problem with the help of dynamic programming.

We can define an array splitArr[] and use it where splitArr[q] represents the minimum number of splits that are required in the prefix string of the length 'q' to split it into the subdivision of prime.

The array splitArr[] is getting filled in the following manner:

• A loop is used for iterating through all of the indices of the input string.
• For each index 'q' from the above loop, another loop begins from 1 to 6 to check whether the substring from the (p + q)th index makes a prime number or not.
• If a prime number is formed, then the value at the array splitArr[] can be updated as: splitArr [p + q] = min(splitArr[p + q], 1 + splitArr[p]);

When all of the values are updated, the value present at the last index is our answer as it contains the least splits number for the complete input string.

FileName: SplitStringPrimes1.java

Output:

For the number 343, the minimum number of splits is: 2 For the number 37, the minimum number of splits is: 1 For the number 44, the minimum number of splits is not possible. For the number 367555, the minimum number of splits is: 4 

Complexity Analysis

The time complexity of the above program is O(N^{3 / 2}), where O(N) time is taken to traverse through all the indices. We also have to check whether the number is prime or not, and this task takes the time complexity of O(N^{1 / 2}). Thus, the total time complexity of the above program is O(N) * O(N^{1 / 2}) = O(N^{3 / 2}), where N is the total number of digits present in the input string.

We know that the prime numbers range from 1 to 10 ^ 6 in this problem. We can use this information for further optimization. Further optimization is possible when we precompute the checks of the prime number and store it in an array. The precomputation is possible with the help of the sieve of the Eratosthenes technique. Observe the following program.

FileName: SplitStringPrimes2.java

Output:

For the number 343, the minimum number of split is: 2 For the number 37, the minimum number of split is: 1 For the number 44, the minimum number of split is not possible. For the number 367555, the minimum number of split is: 4 

Complexity Analysis

It is the most optimized approach as the time complexity of the above program is O(N), where N is the total number of digits present in the input string. Though the time complexity of computing the sieve is O(N * log(N)), we can ignore it as it is computed only once. Thus, unlike other programs, we can check whether a number is a prime number or not in just O(1) time.