// https://www.geeksforgeeks.org/count-of-ways-to-split-a-given-number-into-prime-segments/

​

using System;

public class Program

{

    public static int NumWaysToSplitStringIntoPrimeSegments(string input)

    {

        int count = 0;      

        for (int i = 0; i < Math.Min(input.Length, 6); i++) // max digits of prime number is set to 6

        {

            int n = int.Parse(input.Substring(0, 1 + i));

            Console.Write($"{n}");

            if (isPrimeNumber(n))

            {

                Console.Write($":isPrime ");

                int subCount = 1;

                if (input.Substring(1 + i).Length > 0)

                {

                    // if there is a remaining string, we call function again and pass the remaining string

                    //  and subCount should be what is returned by the function and what is added to (main) count

                    // if there is no remaining string, then it counts as 1 which is why subCount is initialized to 1

                    subCount *= NumWaysToSplitStringIntoPrimeSegments(input.Substring(1 + i));

                    Console.Write($"subcnt:{subCount}");

                }

                count += subCount;

                Console.WriteLine();

            }

            else Console.Write(" ");

        }

        Console.Write($"cnt:{count} ");

        return count;

    }

    private static bool isPrimeNumber(int n)

    {

        if (n < 2) return false; // should be >= 2

        if (n % 2 == 0) return false; // should not be divisible by 2

        for (int i = 3; i < n / 2; i += 2) // should not be divisible by any odd numbers

        {

            if (n % i == 0) return false;

        }

        return true;

    }   

    public static void Main()

    {

        string input = "3175";

        Console.WriteLine($"input: {input}");

        Console.WriteLine($"\noutput: {NumWaysToSplitStringIntoPrimeSegments(input)}");

​

        Console.WriteLine();

        input = "11373";

        Console.WriteLine($"input: {input}");

        Console.WriteLine($"\noutput: {NumWaysToSplitStringIntoPrimeSegments(input)}");

​

        Console.WriteLine();

        input = "100907";

        Console.WriteLine($"input: {input}");

        Console.WriteLine($"\noutput: {NumWaysToSplitStringIntoPrimeSegments(input)}");

    }

}