Task

Partition a positive integer   X   into   N   distinct primes.



Or, to put it in another way:

Find   N   unique primes such that they add up to   X.



Show in the output section the sum   X   and the   N   primes in ascending order separated by plus (+) signs:

     •    partition  99809  with   1 prime.
     •    partition    18   with   2 primes.
     •    partition    19   with   3 primes.
     •    partition    20   with   4 primes.
     •    partition   2017  with  24 primes.
     •    partition  22699  with   1,  2,  3,  and  4  primes.
     •    partition  40355  with   3 primes.

The output could/should be shown in a format such as:

    Partitioned  19  with  3  primes:  3+5+11

   Use any spacing that may be appropriate for the display.
   You need not validate the input(s).
   Use the lowest primes possible;   use  18 = 5+13,   not   18 = 7+11.
   You only need to show one solution.
This task is similar to factoring an integer.



Related tasks

   Count in factors
   Prime decomposition
   Factors of an integer
   Sieve of Eratosthenes
   Primality by trial division
   Factors of a Mersenne number
   Factors of a Mersenne number
   Sequence of primes by trial division


' Partition an integer X into N primes - 29/03/2017
Option Explicit On
 
Module PartitionIntoPrimes
    Dim p(8), a(32), b(32), v, g, q As Long
 
    Sub Main()
        Dim what, t1(), t2(), t3(), xx, nn As String
        Dim x, y, n, m As Long
        what = "99809 1  18 2  19 3  20 4  2017 24  22699 1-4  40355 3"
        t1 = Split(what, "  ")
        For j = 0 To UBound(t1)
            t2 = Split(t1(j)) : xx = t2(0) : nn = t2(1)
            t3 = Split(xx, "-") : x = CLng(t3(0))
            If UBound(t3) = 1 Then y = CLng(t3(1)) Else y = x
            t3 = Split(nn, "-") : n = CLng(t3(0))
            If UBound(t3) = 1 Then m = CLng(t3(1)) Else m = n
            genp(y) 'generate primes in p
            For g = x To y
                For q = n To m : part() : Next 'q
            Next 'g
        Next 'j
    End Sub 'Main
 
    Sub genp(high As Long)
        Dim c, i, k As Long
        Dim bk As Boolean
        p(1) = 2 : p(2) = 3 : c = 2 : i = p(c) + 2
        Do 'i
            k = 2 : bk = False
            Do While k * k <= i And Not bk 'k
                If i Mod p(k) = 0 Then bk = True
                k = k + 1
            Loop 'k
            If Not bk Then
                c = c + 1 : If c > UBound(p) Then ReDim Preserve p(UBound(p) + 8)
                p(c) = i
            End If
            i = i + 2
        Loop Until p(c) > high 'i
    End Sub 'genp
 
    Sub getp(z As Long)
        Dim w As Long
        If a(z) = 0 Then w = z - 1 : a(z) = a(w)
        a(z) = a(z) + 1 : w = a(z) : b(z) = p(w)
    End Sub 'getp
 
    Function list()
        Dim w As String
        w = b(1)
        If v = g Then
            For i = 2 To q : w = w & "+" & b(i) : Next
        Else
            w = "(not possible)"
        End If
        Return "primes: " & w
    End Function 'list
 
    Sub part()
        For i = LBound(a) To UBound(a) : a(i) = 0 : Next 'i
        For i = 1 To q : Call getp(i) : Next 'i
        Do While True : v = 0
            For s = 1 To q
                v = v + b(s)
                If v > g Then
                    If s = 1 Then Exit Do
                    For k = s To q : a(k) = 0 : Next 'k
                    For r = s - 1 To q : Call getp(r) : Next 'r
                    Continue Do
                End If
            Next 's
            If v = g Then Exit Do
            If v < g Then Call getp(q)
        Loop
        Console.WriteLine("partition " & g & " into " & q & " " & list())
    End Sub 'part
 
End Module 'PartitionIntoPrimes
 