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


NextPrimeMemo[n_] := (NextPrimeMemo[n] = NextPrime[n]);(*This improves performance by 30% or so*)
PrimeList[count_] := Prime/@Range[count];(*Just a helper to create an initial list of primes of the desired length*)
AppendPrime[list_] := Append[list,NextPrimeMemo[Last@list]];(*Another helper that makes creating the next candidate less verbose*)
 
NextCandidate[{list_, target_}] :=
 With[
  {len = Length@list, nextHead = NestWhile[Drop[#, -1] &, list, Total[#] > target &]},
  Which[
   {} == nextHead, {{}, target},
   Total[nextHead] == target && Length@nextHead == len, {nextHead, target},
   True, {NestWhile[AppendPrime, MapAt[NextPrimeMemo, nextHead, -1], Length[#] < Length[list] &], target}
   ]
  ];(*This is the meat of the matter. If it determines that the job is impossible, it returns a structure with an empty list of summands. If the input satisfies the success criteria, it just returns it (this will be our fixed point). Otherwise, it generates a subsequent candidate.*)
 
FormatResult[{list_, number_}, targetCount_] := 
 StringForm[
  "Partitioned `1` with `2` prime`4`: `3`", 
  number, 
  targetCount, 
  If[0 == Length@list, "no solutions found", StringRiffle[list, "+"]],
  If[1 == Length@list, "", "s"]]; (*Just a helper for pretty-printing the output*)
 
PrimePartition[number_, count_] := FixedPoint[NextCandidate, {PrimeList[count], number}];(*This is where things kick off. NextCandidate will eventually return the failure format or a success, and either of those are fixed points of the function.*)
 
TestCases =
  {
   {99809, 1},
   {18, 2},
   {19, 3},
   {20, 4},
   {2017, 24},
   {22699, 1},
   {22699, 2},
   {22699, 3},
   {22699, 4},
   {40355, 3}
   };
 
TimedResults = ReleaseHold[Hold[AbsoluteTiming[FormatResult[PrimePartition @@ #, Last@#]]] & /@TestCases](*I thought it would be interesting to include the timings, which are in seconds*)
 
TimedResults // TableForm