using System;

using System.Collections.Generic;

using System.Linq;

​

class PrimePartitions

{

    // Check if a number is prime

    static bool IsPrime(int num)

    {

        if (num < 2) return false;

        for (int i = 2; i * i <= num; i++)

        {

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

        }

        return true;

    }

​

    // Generate a list of primes up to n

    static List<int> GetPrimes(int n)

    {

        List<int> primes = new List<int>();

        for (int i = 2; i <= n; i++)

        {

            if (IsPrime(i))

                primes.Add(i);

        }

        return primes;

    }

​

    // Find all unique partitions that sum to the given number

    static void FindPrimePartitions(int target, List<int> primes, List<int> currentPartition, int start)

    {

        int sum = currentPartition.Sum();

        if (sum == target)

        {

            Console.Write(target + " = " + string.Join(" + ", currentPartition));

            Console.WriteLine($" ({currentPartition.Count} numbers)");

            return;

        }

        if (sum > target) return;

​

        for (int i = start; i < primes.Count; i++)

        {

            currentPartition.Add(primes[i]);

            FindPrimePartitions(target, primes, currentPartition, i + 1);

            currentPartition.RemoveAt(currentPartition.Count - 1);

        }

    }

​

    static void Main()

    {

        Console.Write("Please enter an integer: ");

        if (int.TryParse(Console.ReadLine(), out int input))

        {

            List<int> primes = GetPrimes(input);

            List<int> currentPartition = new List<int>();

​

            FindPrimePartitions(input, primes, currentPartition, 0);

​

            Console.WriteLine($"{input} has {CountPrimePartitions(input, primes, 0)} unique prime partitions!");

        }

        else

        {

            Console.WriteLine("Invalid input. Please enter a valid integer.");

        }

    }

​

    // Count the number of unique prime partitions

    static int CountPrimePartitions(int target, List<int> primes, int start)

    {

        if (target == 0) return 1;

        if (target < 0 || start >= primes.Count) return 0;

​

        int count = 0;

        for (int i = start; i < primes.Count; i++)

        {

            count += CountPrimePartitions(target - primes[i], primes, i + 1);

        }

        return count;

    }

}