user
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
assistant
(formerly Perl 6)

Attempt This Online!

```
# short circuit for '1' partition
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! () }

my @primes = lazy (^Inf).grep: &is-prime;

multi partition ( Int $number, Int $parts where * > 1 = 2 ) {
    my @these = @primes[^($number div $parts)];
    shift @these if (($number %% 2) && ($parts %% 2)) || (($number % 2) && ($parts % 2));
    for @these.combinations($parts - 1) { 
        my $maybe = $number - .sum;
        return (|$_, $maybe) if $maybe.is-prime && ($maybe ∉ $_)
    };
    ()
}

# TESTING
(18,2, 19,3, 20,4, 99807,1, 99809,1, 99820,6, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3)\
  .race(:1batch).map: -> $number, $parts {
    say (sprintf "Partition %5d into %2d prime piece", $number, $parts),
    $parts == 1 ?? ':  ' !! 's: ', join '+', partition($number, $parts) || 'not possible'
}

```

Output:

```
Partition    18 into  2 prime pieces: 5+13
Partition    19 into  3 prime pieces: 3+5+11
Partition    20 into  4 prime pieces: not possible
Partition 99807 into  1 prime piece:  not possible
Partition 99809 into  1 prime piece:  99809
Partition 99820 into  6 prime pieces: 3+5+7+11+61+99733
Partition  2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partition 22699 into  1 prime piece:  22699
Partition 22699 into  2 prime pieces: 2+22697
Partition 22699 into  3 prime pieces: 3+5+22691
Partition 22699 into  4 prime pieces: 2+3+43+22651
Partition 40355 into  3 prime pieces: 3+139+40213
```