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


----------------------------------------
-- returns a sorted list of the <cnt> smallest unique primes that add up to <n>,
-- or FALSE if there is no such partition of primes for <n>
----------------------------------------
on getPrimePartition (n, cnt,   primes, ptr, res)
    if voidP(primes) then 
        primes = _global.sieve.getPrimesInRange(2, n)
        ptr = 1
        res = []
    end if  
    if cnt=1 then
        if primes.getPos(n)>=ptr then
            res.addAt(1, n)
            if res.count=cnt+ptr-1 then
                return res
            end if
            return TRUE
        end if
    else
        repeat with i = ptr to primes.count
            p = primes[i]
            ok = getPrimePartition(n-p, cnt-1,   primes, i+1, res)
            if ok then
                res.addAt(1, p)
                if res.count=cnt+ptr-1 then
                    return res
                end if
                return TRUE
            end if
        end repeat
    end if
    return FALSE
end
 
----------------------------------------
-- gets partition, prints formatted result
----------------------------------------
on showPrimePartition (n, cnt)
    res = getPrimePartition(n, cnt) 
    if res=FALSE then res = "not prossible"
    else res = implode("+", res)
    put "Partitioned "&n&" with "&cnt&" primes: " & res
end
 
----------------------------------------
-- implodes list into string
----------------------------------------
on implode (delim, tList)
    str = ""
    repeat with i=1 to tList.count
        put tList[i]&delim after str
    end repeat
    delete char (str.length+1-delim.length) to str.length of str
    return str
end