Partition an integer x into n primes

Partition an integer x into n primes
You are encouraged to solve this task according to the task description, using any language you may know.

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

11l

Translation of: D

F is_prime(a)
   R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0)))

F generate_primes(n)
   V r = [2]
   V i = 3
   L
      I is_prime(i)
         r.append(i)
         I r.len == n
            L.break
      i += 2
   R r

V primes = generate_primes(50'000)

F find_combo(k, x, m, n, &combo)
   I k >= m
      I sum(combo.map(idx -> :primes[idx])) == x
         print(‘Partitioned #5 with #2 #.: ’.format(x, m, I m > 1 {‘primes’} E ‘prime ’), end' ‘’)
         L(i) 0 .< m
            print(:primes[combo[i]], end' I i < m - 1 {‘+’} E "\n")
         R 1B
   E
      L(j) 0 .< n
         I k == 0 | j > combo[k - 1]
            combo[k] = j
            I find_combo(k + 1, x, m, n, &combo)
               R 1B
   R 0B

F partition(x, m)
   V n = :primes.filter(a -> a <= @x).len
   V combo = [0] * m
   I !find_combo(0, x, m, n, &combo)
      print(‘Partitioned #5 with #2 #.: (not possible)’.format(x, m, I m > 1 {‘primes’} E ‘prime ’))

V data = [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
          (22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)]

L(n, cnt) data
   partition(n, cnt)

Output:

Partitioned 99809 with  1 prime : 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime : 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

ALGOL 68

BEGIN # find the lowest n distinct primes that sum to an integer x           #

    INT max number = 100 000;              # largest number we will consider #
    # sieve the primes to max number                                         #
    [ 1 : max number ]BOOL prime; FOR i TO UPB prime DO prime[ i ] := ODD i OD;
    prime[ 1 ] := FALSE;
    prime[ 2 ] := TRUE;
    FOR s FROM 3 BY 2 TO ENTIER sqrt( max number ) DO
        IF prime[ s ] THEN
            FOR p FROM s * s BY s TO UPB prime DO prime[ p ] := FALSE OD
        FI
    OD;

    [ 1 : 0 ]INT no partition;       # empty array - used if can't partition #

    # returns n partitioned into p primes or an empty array if n can't be    #
    #         partitioned into p primes, the first prime to try is in start  #
    PROC partition from = ( INT n, p, start )[]INT:
         IF   p < 1 OR n < 2 OR start < 2 THEN          # invalid parameters #
            no partition
         ELIF p = 1 THEN          # partition into 1 prime - n must be prime #
            IF NOT prime[ n ] THEN no partition ELSE n FI
         ELIF p = 2 THEN                   # partition into a pair of primes #
            INT  half n = n OVER 2;
            INT  p1    := 0, p2 := 0;
            BOOL found := FALSE;
            FOR p pos FROM start TO UPB prime WHILE NOT found AND p pos < half n DO
                IF prime[ p pos ] THEN
                    p1    := p pos;
                    p2    := n - p pos;
                    found := prime[ p2 ]
                FI
            OD;
            IF NOT found THEN no partition ELSE ( p1, p2 ) FI
         ELSE                              # partition into 3 or more primes #
            [ 1 : p ]INT p2;
            INT  half n = n OVER 2;
            INT  p1    := 0;
            BOOL found := FALSE;
            FOR p pos FROM start TO UPB prime WHILE NOT found AND p pos < half n DO
                IF prime[ p pos ] THEN
                    p1    := p pos;
                    []INT sub partition = partition from( n - p1, p - 1, p pos + 1 );
                    IF found := UPB sub partition = p - 1 THEN
                        # have p - 1 primes summing to n - p1                #
                        p2[ 1 ]     := p1;
                        p2[ 2 : p ] := sub partition
                    FI
                FI
            OD;
            IF NOT found THEN no partition ELSE p2 FI
         FI # partition from # ;

    # returns the partition of n into p primes or an empty array if that is  #
    #         not possible                                                   #
    PROC partition = ( INT n, p )[]INT: partition from( n, p, 2 );

    # show the first partition of n into p primes, if that is possible       #
    PROC show partition = ( INT n, p )VOID:
         BEGIN
            []INT primes = partition( n, p );
            STRING partition info = whole( n, -6 ) + " with " + whole( p, -2 )
                                  + " prime" + IF p = 1 THEN " " ELSE "s" FI + ": ";
            IF UPB primes < LWB primes THEN
                print( ( "Partitioning ", partition info, "is not possible" ) )
            ELSE
                print( ( "Partitioned  ", partition info ) );
                print( ( whole( primes[ LWB primes ], 0 ) ) );
                FOR p pos FROM LWB primes + 1 TO UPB primes DO
                    print( ( "+", whole( primes[ p pos ], 0 ) ) )
                OD
            FI;
            print( ( newline ) )
         END # show partition # ;

    # test cases                                                             #
    show partition( 99809,  1 );
    show partition(    18,  2 );
    show partition(    19,  3 );
    show partition(    20,  4 );
    show partition(  2017, 24 );
    show partition( 22699,  1 );
    show partition( 22699,  2 );
    show partition( 22699,  3 );
    show partition( 22699,  4 );
    show partition( 40355,  3 )

END

Output:

Partitioned   99809 with  1 prime : 99809
Partitioned      18 with  2 primes: 5+13
Partitioned      19 with  3 primes: 3+5+11
Partitioning     20 with  4 primes: is not possible
Partitioned    2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned   22699 with  1 prime : 22699
Partitioned   22699 with  2 primes: 2+22697
Partitioned   22699 with  3 primes: 3+5+22691
Partitioned   22699 with  4 primes: 2+3+43+22651
Partitioned   40355 with  3 primes: 3+139+40213

APL

Works with: Dyalog APL

primepart←{
    sieve←{
        (⊃{0@(1↓⍺×⍳⌊(⍴⍵)÷⍺)⊢⍵}/(1↓⍳⍵),⊂(0,1↓⍵/1))/⍳⍵
    }
    part←{
        0=⍴⍺⍺:⍬
        ⍵=1:(⍺⍺=⍺)/⍺⍺
        0≠⍴r←(⍺-⊃⍺⍺)((1↓⍺⍺)∇∇)⍵-1:(⊃⍺⍺),r
        ⍺((1↓⍺⍺)∇∇)⍵
    }
    ⍺((sieve ⍺)part)⍵
}
primepart_test←{
    tests←(99809 1)(18 2)(19 3)(20 4)(2017 24)
    tests,←(22699 1)(22699 2)(22699 3)(22699 4)(40355 3)
    {
        x n←⍵
        p←x primepart n
        ⍞←'Partition ',(⍕x),' with ',(⍕n),' primes: '
        0=⍴p:⍞←'not possible.',⎕TC[2]
        ⍞←(1↓∊'+',¨⍕¨p),⎕TC[2]
    }¨tests
}

Output:

      primepart_test⍬
Partition 99809 with 1 primes: 99809
Partition 18 with 2 primes: 5+13
Partition 19 with 3 primes: 3+5+11
Partition 20 with 4 primes: not possible.
Partition 2017 with 24 primes: 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 with 1 primes: 22699
Partition 22699 with 2 primes: 2+22697
Partition 22699 with 3 primes: 3+5+22691
Partition 22699 with 4 primes: 2+3+43+22651
Partition 40355 with 3 primes: 3+139+40213

BCPL

get "libhdr"

let sieve(n, prime) be
$(  let i = 2
    0!prime := false
    1!prime := false
    for i = 2 to n do i!prime := true
    while i*i <= n
    $(  let j = i*i
        while j <= n
        $(  j!prime := false
            j := j+i
        $)
        i := i+1
    $)
$)

let partition(x, n, prime, p, part) =
    p > x -> false,
    n = 1 -> valof $( !part := x; resultis x!prime $),
    valof
    $(  p := p+1 repeatuntil p!prime
        !part := p
        if partition(x-p, n-1, prime, p, part+1) resultis true
        resultis partition(x, n, prime, p, part)
    $)

let showpart(n, part) be
$(  writef("%N", !part)
    unless n=1 do
    $(  wrch('+')
        showpart(n-1, part+1)
    $)
$)

let show(x, n, prime) be
$(  let part = vec 32
    writef("Partitioned %N with %N prime%S: ", x, n, n=1->"", "s")
    test partition(x, n, prime, 1, part)
        do showpart(n, part)
        or writes("not possible")
    newline()
$)

let start() be
$(  let prime = getvec(100000)

    let tests = table 99809,1, 18,2, 19,3, 20,4, 2017,24,
                      22699,1, 22699,2, 22699,3, 22699,4, 40355,3

    sieve(100000, prime)
    for t = 0 to 9 do show(tests!(t*2), tests!(t*2+1), prime)
    freevec(prime)
$)

Output:

Partitioned 99809 with 1 prime: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 prime: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213

C

Works with: C99

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct bit_array_tag {
    uint32_t size;
    uint32_t* array;
} bit_array;

bool bit_array_create(bit_array* b, uint32_t size) {
    uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t));
    if (array == NULL)
        return false;
    b->size = size;
    b->array = array;
    return true;
}

void bit_array_destroy(bit_array* b) {
    free(b->array);
    b->array = NULL;
}

void bit_array_set(bit_array* b, uint32_t index, bool value) {
    assert(index < b->size);
    uint32_t* p = &b->array[index >> 5];
    uint32_t bit = 1 << (index & 31);
    if (value)
        *p |= bit;
    else
        *p &= ~bit;
}

bool bit_array_get(const bit_array* b, uint32_t index) {
    assert(index < b->size);
    uint32_t bit = 1 << (index & 31);
    return (b->array[index >> 5] & bit) != 0;
}

typedef struct sieve_tag {
    uint32_t limit;
    bit_array not_prime;
} sieve;

bool sieve_create(sieve* s, uint32_t limit) {
    if (!bit_array_create(&s->not_prime, limit + 1))
        return false;
    bit_array_set(&s->not_prime, 0, true);
    bit_array_set(&s->not_prime, 1, true);
    for (uint32_t p = 2; p * p <= limit; ++p) {
        if (bit_array_get(&s->not_prime, p) == false) {
            for (uint32_t q = p * p; q <= limit; q += p)
                bit_array_set(&s->not_prime, q, true);
        }
    }
    s->limit = limit;
    return true;
}

void sieve_destroy(sieve* s) {
    bit_array_destroy(&s->not_prime);
}

bool is_prime(const sieve* s, uint32_t n) {
    assert(n <= s->limit);
    return bit_array_get(&s->not_prime, n) == false;
}

bool find_prime_partition(const sieve* s, uint32_t number, uint32_t count,
                          uint32_t min_prime, uint32_t* p) {
    if (count == 1) {
        if (number >= min_prime && is_prime(s, number)) {
            *p = number;
            return true;
        }
        return false;
    }
    for (uint32_t prime = min_prime; prime < number; ++prime) {
        if (!is_prime(s, prime))
            continue;
        if (find_prime_partition(s, number - prime, count - 1,
                                 prime + 1, p + 1)) {
            *p = prime;
            return true;
        }
    }
    return false;
}

void print_prime_partition(const sieve* s, uint32_t number, uint32_t count) {
    assert(count > 0);
    uint32_t* primes = malloc(count * sizeof(uint32_t));
    if (primes == NULL) {
        fprintf(stderr, "Out of memory\n");
        return;
    }
    if (!find_prime_partition(s, number, count, 2, primes)) {
        printf("%u cannot be partitioned into %u primes.\n", number, count);
    } else {
        printf("%u = %u", number, primes[0]);
        for (uint32_t i = 1; i < count; ++i)
            printf(" + %u", primes[i]);
        printf("\n");
    }
    free(primes);
}

int main() {
    const uint32_t limit = 100000;
    sieve s = { 0 };
    if (!sieve_create(&s, limit)) {
        fprintf(stderr, "Out of memory\n");
        return 1;
    }
    print_prime_partition(&s, 99809, 1);
    print_prime_partition(&s, 18, 2);
    print_prime_partition(&s, 19, 3);
    print_prime_partition(&s, 20, 4);
    print_prime_partition(&s, 2017, 24);
    print_prime_partition(&s, 22699, 1);
    print_prime_partition(&s, 22699, 2);
    print_prime_partition(&s, 22699, 3);
    print_prime_partition(&s, 22699, 4);
    print_prime_partition(&s, 40355, 3);
    sieve_destroy(&s);
    return 0;
}

Output:

99809 = 99809
18 = 5 + 13
19 = 3 + 5 + 11
20 cannot be partitioned into 4 primes.
2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
22699 = 22699
22699 = 2 + 22697
22699 = 3 + 5 + 22691
22699 = 2 + 3 + 43 + 22651
40355 = 3 + 139 + 40213

C#

Works with: C sharp version 7

using System;
using System.Collections;
using System.Collections.Generic;
using static System.Linq.Enumerable;

public static class Rosetta
{
    static void Main()
    {
        foreach ((int x, int n) in new [] {
            (99809, 1),
            (18, 2),
            (19, 3),
            (20, 4),
            (2017, 24),
            (22699, 1),
            (22699, 2),
            (22699, 3),
            (22699, 4),
            (40355, 3)
        }) {
            Console.WriteLine(Partition(x, n));
        }
    }

    public static string Partition(int x, int n) {
        if (x < 1 || n < 1) throw new ArgumentOutOfRangeException("Parameters must be positive.");
        string header = $"{x} with {n} {(n == 1 ? "prime" : "primes")}: ";
        int[] primes = SievePrimes(x).ToArray();
        if (primes.Length < n) return header + "not enough primes";
        int[] solution = CombinationsOf(n, primes).FirstOrDefault(c => c.Sum() == x);
        return header + (solution == null ? "not possible" : string.Join("+", solution);
    }

    static IEnumerable<int> SievePrimes(int bound) {
        if (bound < 2) yield break;
        yield return 2;

        BitArray composite = new BitArray((bound - 1) / 2);
        int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
        for (int i = 0; i < limit; i++) {
            if (composite[i]) continue;
            int prime = 2 * i + 3;
            yield return prime;
            for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime) composite[j] = true;
        }
        for (int i = limit; i < composite.Count; i++) {
            if (!composite[i]) yield return 2 * i + 3;
        }
    }

    static IEnumerable<int[]> CombinationsOf(int count, int[] input) {
        T[] result = new T[count];
        foreach (int[] indices in Combinations(input.Length, count)) {
            for (int i = 0; i < count; i++) result[i] = input[indices[i]];
            yield return result;
        }
    }

    static IEnumerable<int[]> Combinations(int n, int k) {
        var result = new int[k];
        var stack = new Stack<int>();
        stack.Push(0);
        while (stack.Count > 0) {
            int index = stack.Count - 1;
            int value = stack.Pop();
            while (value < n) {
                result[index++] = value++;
                stack.Push(value);
                if (index == k) {
                    yield return result;
                    break;
                }
            }
        }
    }

}

Output:

99809 with 1 prime: 99809
18 with 2 primes: 5+13
19 with 3 primes: 3+5+11
20 with 4 primes: not possible
2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
22699 with 1 prime: 22699
22699 with 2 primes: 2+22697
22699 with 3 primes: 3+5+22691
22699 with 4 primes: 2+3+43+22651
40355 with 3 primes: 3+139+40213

C++

Translation of: D

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

std::vector<int> primes;

struct Seq {
public:
    bool empty() {
        return p < 0;
    }

    int front() {
        return p;
    }

    void popFront() {
        if (p == 2) {
            p++;
        } else {
            p += 2;
            while (!empty() && !isPrime(p)) {
                p += 2;
            }
        }
    }

private:
    int p = 2;

    bool isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        if (n % 3 == 0) return n == 3;

        int d = 5;
        while (d * d <= n) {
            if (n % d == 0) return false;
            d += 2;
            if (n % d == 0) return false;
            d += 4;
        }
        return true;
    }
};

// generate the first 50,000 primes and call it good
void init() {
    Seq seq;

    while (!seq.empty() && primes.size() < 50000) {
        primes.push_back(seq.front());
        seq.popFront();
    }
}

bool findCombo(int k, int x, int m, int n, std::vector<int>& combo) {
    if (k >= m) {
        int sum = 0;
        for (int idx : combo) {
            sum += primes[idx];
        }

        if (sum == x) {
            auto word = (m > 1) ? "primes" : "prime";
            printf("Partitioned %5d with %2d %s ", x, m, word);
            for (int idx = 0; idx < m; ++idx) {
                std::cout << primes[combo[idx]];
                if (idx < m - 1) {
                    std::cout << '+';
                } else {
                    std::cout << '\n';
                }
            }
            return true;
        }
    } else {
        for (int j = 0; j < n; j++) {
            if (k == 0 || j > combo[k - 1]) {
                combo[k] = j;
                bool foundCombo = findCombo(k + 1, x, m, n, combo);
                if (foundCombo) {
                    return true;
                }
            }
        }
    }

    return false;
}

void partition(int x, int m) {
    if (x < 2 || m < 1 || m >= x) {
        throw std::runtime_error("Invalid parameters");
    }

    std::vector<int> filteredPrimes;
    std::copy_if(
        primes.cbegin(), primes.cend(),
        std::back_inserter(filteredPrimes),
        [x](int a) { return a <= x; }
    );

    int n = filteredPrimes.size();
    if (n < m) {
        throw std::runtime_error("Not enough primes");
    }

    std::vector<int> combo;
    combo.resize(m);
    if (!findCombo(0, x, m, n, combo)) {
        auto word = (m > 1) ? "primes" : "prime";
        printf("Partitioned %5d with %2d %s: (not possible)\n", x, m, word);
    }
}

int main() {
    init();

    std::vector<std::pair<int, int>> a{
        {99809,  1},
        {   18,  2},
        {   19,  3},
        {   20,  4},
        { 2017, 24},
        {22699,  1},
        {22699,  2},
        {22699,  3},
        {22699,  4},
        {40355,  3}
    };

    for (auto& p : a) {
        partition(p.first, p.second);
    }

    return 0;
}

Output:

Partitioned 99809 with  1 prime 99809
Partitioned    18 with  2 primes 5+13
Partitioned    19 with  3 primes 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime 22699
Partitioned 22699 with  2 primes 2+22697
Partitioned 22699 with  3 primes 3+5+22691
Partitioned 22699 with  4 primes 2+3+43+22651
Partitioned 40355 with  3 primes 3+139+40213

CLU

isqrt = proc (s: int) returns (int)
    x0: int := s/2
    if x0 = 0 then return(s) end
    x1: int := (x0 + s/x0) / 2
    while x1 < x0 do
        x0, x1 := x1, (x0 + s/x0) / 2
    end
    return(x0)
end isqrt

primes = proc (n: int) returns (sequence[int])
    prime: array[bool] := array[bool]$fill(1, n, true)
    prime[1] := false
    for p: int in int$from_to(2, isqrt(n)) do
        for c: int in int$from_to_by(p*p, n, p) do
            prime[c] := false
        end
    end

    pr: array[int] := array[int]$predict(1, n)
    for p: int in array[bool]$indexes(prime) do
        if prime[p] then array[int]$addh(pr, p) end
    end

    return(sequence[int]$a2s(pr))
end primes

partition_sum = proc (x, n: int, nums: sequence[int])
                returns (sequence[int])
                signals (impossible)
    if n<=0 cor sequence[int]$empty(nums) then signal impossible end

    if n=1 then
        for k: int in sequence[int]$elements(nums) do
            if x=k then return(sequence[int]$[x]) end
        end
        signal impossible
    end

    k: int := sequence[int]$bottom(nums)
    rest: sequence[int] := sequence[int]$reml(nums)

    return(sequence[int]$addl(partition_sum(x-k, n-1, rest), k))
    except when impossible:
        return(partition_sum(x, n, rest))
        resignal impossible
    end
end partition_sum

prime_partition = proc (x, n: int)
                  returns (sequence[int])
                  signals (impossible)
    return(partition_sum(x, n, primes(x))) resignal impossible
end prime_partition

format_sum = proc (nums: sequence[int]) returns (string)
    result: string := ""
    for n: int in sequence[int]$elements(nums) do
        result := result || "+" || int$unparse(n)
    end
    return(string$rest(result, 2))
end format_sum

start_up = proc ()
    test = struct[x: int, n: int]
    tests: sequence[test] := sequence[test]$[
        test${x:99809,n:1}, test${x:18,n:2}, test${x:19,n:3}, test${x:20,n:4},
        test${x:2017,n:24}, test${x:22699,n:1}, test${x:22699,n:2},
        test${x:22699,n:3}, test${x:22699,n:4}, test${x:40355,n:3}
    ]

    po: stream := stream$primary_output()
    for t: test in sequence[test]$elements(tests) do
        stream$puts(po, "Partitioned " || int$unparse(t.x) || " with "
                    || int$unparse(t.n) || " primes: ")
        stream$putl(po, format_sum(prime_partition(t.x, t.n)))
        except when impossible:
            stream$putl(po, "not possible.")
        end
    end
end start_up

Output:

Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible.
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213

Cowgol

include "cowgol.coh";

const MAXPRIM := 100000;
const MAXPRIM_B := (MAXPRIM >> 3) + 1;

var primebits: uint8[MAXPRIM_B];
typedef ENTRY_T is @indexof primebits;

sub pentry(n: uint32): (ent: ENTRY_T, bit: uint8) is
    ent := (n >> 3) as ENTRY_T;
    bit := (n & 7) as uint8;
end sub;

sub setprime(n: uint32, prime: uint8) is
    var ent: ENTRY_T;
    var bit: uint8;
    (ent, bit) := pentry(n);
    var one: uint8 := 1;
    primebits[ent] := primebits[ent] & ~(one << bit);
    primebits[ent] := primebits[ent] | (prime << bit);
end sub;

sub prime(n: uint32): (prime: uint8) is
    var ent: ENTRY_T;
    var bit: uint8;
    (ent, bit) := pentry(n);
    prime := (primebits[ent] >> bit) & 1;
end sub;

sub sieve() is
    MemSet(&primebits[0], 0xFF, @bytesof primebits);
    setprime(0, 0);
    setprime(1, 0);
    var p: uint32 := 2;
    while p*p <= MAXPRIM loop
        var c := p*p;
        while c <= MAXPRIM loop
            setprime(c, 0);
            c := c + p;
        end loop;
        p := p + 1;
    end loop;
end sub;

sub nextprime(p: uint32): (r: uint32) is
    r := p;
    loop
        r := r + 1;
        if prime(r) != 0 then break; end if;
    end loop;
end sub;

sub partition(x: uint32, n: uint8, part: [uint32]): (r: uint8) is
    record State is
        x: uint32;
        n: uint8;
        p: uint32;
        part: [uint32];
    end record;

    var stack: State[128];
    var sp: @indexof stack := 0;

    sub Push(x: uint32, n: uint8, p: uint32, part: [uint32]) is
        stack[sp].x := x;
        stack[sp].n := n;
        stack[sp].p := p;
        stack[sp].part := part;
        sp := sp + 1;
    end sub;

    sub Pull(): (x: uint32, n: uint8, p: uint32, part: [uint32]) is
        sp := sp - 1;
        x := stack[sp].x;
        n := stack[sp].n;
        p := stack[sp].p;
        part := stack[sp].part;
    end sub;

    r := 0;
    Push(x, n, 1, part);
    while sp > 0 loop
        var p: uint32;
        (x, n, p, part) := Pull();
        p := nextprime(p);

        if x < p then
            continue;
        end if;

        if n == 1 then
            if prime(x) != 0 then
                r := 1;
                [part] := x;
                return;
            end if;
        else
            [part] := p;
            Push(x, n, p, part);
            Push(x-p, n-1, p, @next part);
        end if;
    end loop;
    r := 0;
end sub;

sub showpartition(x: uint32, n: uint8) is
    print("Partitioning ");
    print_i32(x);
    print(" with ");
    print_i8(n);
    print(" primes: ");

    var part: uint32[64];
    if partition(x, n, &part[0]) != 0 then
        print_i32(part[0]);
        var i: @indexof part := 1;
        while i < n as @indexof part loop
            print_char('+');
            print_i32(part[i]);
            i := i + 1;
        end loop;
    else
        print("Not possible");
    end if;
    print_nl();
end sub;

sieve();

record Test is
    x: uint32;
    n: uint8;
end record;

var tests: Test[] := {
    {99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
    {22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}
};

var test: @indexof tests := 0;
while test < @sizeof tests loop
    showpartition(tests[test].x, tests[test].n);
    test := test + 1;
end loop;

Output:

Partitioning 99809 with 1 primes: 99809
Partitioning 18 with 2 primes: 5+13
Partitioning 19 with 3 primes: 3+5+11
Partitioning 20 with 4 primes: Not possible
Partitioning 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioning 22699 with 1 primes: 22699
Partitioning 22699 with 2 primes: 2+22697
Partitioning 22699 with 3 primes: 3+5+22691
Partitioning 22699 with 4 primes: 2+3+43+22651
Partitioning 40355 with 3 primes: 3+139+40213

D

Translation of: Kotlin

import std.array : array;
import std.range : take;
import std.stdio;

bool isPrime(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;

    int d = 5;
    while (d*d <= n) {
        if (n % d == 0) return false;
        d += 2;
        if (n % d == 0) return false;
        d += 4;
    }
    return true;
}

auto generatePrimes() {
    struct Seq {
        int p = 2;

        bool empty() {
            return p < 0;
        }

        int front() {
            return p;
        }

        void popFront() {
            if (p==2) {
                p++;
            } else {
                p += 2;
                while (!empty && !p.isPrime) {
                    p += 2;
                }
            }
        }
    }

    return Seq();
}

bool findCombo(int k, int x, int m, int n, int[] combo) {
    import std.algorithm : map, sum;
    auto getPrime = function int(int idx) => primes[idx];

    if (k >= m) {
        if (combo.map!getPrime.sum == x) {
            auto word = (m > 1) ? "primes" : "prime";
            writef("Partitioned %5d with %2d %s ", x, m, word);
            foreach (i; 0..m) {
                write(primes[combo[i]]);
                if (i < m-1) {
                    write('+');
                } else {
                    writeln();
                }
            }
            return true;
        }
    } else {
        foreach (j; 0..n) {
            if (k==0 || j>combo[k-1]) {
                combo[k] = j;
                bool foundCombo = findCombo(k+1, x, m, n, combo);
                if (foundCombo) {
                    return true;
                }
            }
        }
    }
    return false;
}

void partition(int x, int m) {
    import std.exception : enforce;
    import std.algorithm : filter;
    enforce(x>=2 && m>=1 && m<x);

    auto lessThan = delegate int(int a) => a<=x;
    auto filteredPrimes = primes.filter!lessThan.array;
    auto n = filteredPrimes.length;
    enforce(n>=m, "Not enough primes");

    int[] combo = new int[m];
    if (!findCombo(0, x, m, n, combo)) {
        auto word = (m > 1) ? "primes" : "prime";
        writefln("Partitioned %5d with %2d %s: (not possible)", x, m, word);
    }
}

int[] primes;
void main() {
    // generate first 50,000 and call it good
    primes = generatePrimes().take(50_000).array;

    auto a = [
        [99809,  1],
        [   18,  2],
        [   19,  3],
        [   20,  4],
        [ 2017, 24],
        [22699,  1],
        [22699,  2],
        [22699,  3],
        [22699,  4],
        [40355,  3]
    ];

    foreach(p; a) {
        partition(p[0], p[1]);
    }
}

Output:

Partitioned 99809 with  1 prime 99809
Partitioned    18 with  2 primes 5+13
Partitioned    19 with  3 primes 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime 22699
Partitioned 22699 with  2 primes 2+22697
Partitioned 22699 with  3 primes 3+5+22691
Partitioned 22699 with  4 primes 2+3+43+22651
Partitioned 40355 with  3 primes 3+139+40213

F#

This task uses Extensible Prime Generator (F#)

// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017
let rcTask n ng =
  let rec fN i g e l = seq{
    match i with
    |1 -> if isPrime g then yield Some (g::e) else yield None
    |_ -> yield! Seq.mapi (fun n a->fN (i-1) (g-a) (a::e) (Seq.skip (n+1) l)) (l|>Seq.takeWhile(fun n->(g-n)>n))|>Seq.concat}
  match fN n ng [] primes |> Seq.tryPick id with
    |Some n->printfn "%d is the sum of %A" ng n
    |_     ->printfn "No Solution"

Output:

rcTask 1 99089 -> 99089 is the sum of [99089]
rcTask 2 18    -> 18 is the sum of [13; 5]
rcTask 3 19    -> 19 is the sum of [11; 5; 3]
rcTask 4 20    -> No Solution
rcTask 24 2017 -> 2017 is the sum of [1129; 97; 79; 73; 71; 67; 61; 59; 53; 47; 43; 41; 37; 31; 29; 23; 19; 17; 13; 11; 7; 5; 3; 2]
rcTask 1 2269  -> 2269 is the sum of [2269]
rcTask 2 2269  -> 2269 is the sum of [2267; 2]
rcTask 3 2269  -> 2269 is the sum of [2243; 23; 3]
rcTask 4 2269  -> 2269 is the sum of [2251; 13; 3; 2]
rcTask 3 40355 -> 40355 is the sum of [40213; 139; 3]

Factor

USING: formatting fry grouping kernel math.combinatorics
math.parser math.primes sequences ;

: partition ( x n -- str )
    over [ primes-upto ] 2dip '[ sum _ = ] find-combination
    [ number>string ] map "+" join ;
    
: print-partition ( x n seq -- )
    [ "no solution" ] when-empty
    "Partitioned %5d with %2d primes: %s\n" printf ;
    
{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699
  4 40355 3 } 2 group
[ first2 2dup partition print-partition ] each

Output:

Partitioned 99809 with  1 primes: 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: no solution
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 primes: 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

Fortran

Translation of: VBScript

 
   module primes_module
    implicit none
    integer,allocatable :: p(:)
    integer :: a(0:32), b(0:32)
    integer,private :: sum_primes, number
    contains
!
    subroutine setnum(val)
        implicit none
        integer :: val
        number = val
        return
    end subroutine setnum
!
    subroutine init(thesize)
    implicit none
    integer :: thesize
    !
    allocate(p(thesize))
    p=0
    a=0
    b=0
    return
    end subroutine init
!
    subroutine genp(high) ! Store all primes up to high in the array p
        integer, intent(in) :: high
        integer :: i, numprimes, j,k
        logical*1 :: bk(0:high)
        !
        bk = .false.
        p = 0
        a = 0
        b = 0
        call eratosthenes(bk , high)
        j = 0
        numprimes = count(bk)
        k = 0
        do i = 1,high
            if(bk(i))then
                j = j+1
                p(j) = i
                if(j==numprimes)exit    !No need to loop more, all primes stored
            endif
        end do
        print*,'numprimes',numprimes, i,p(j)
        return
    end subroutine genp

    subroutine getp(z) ! used to update the zth prime number in the sequence of primes that are being used to partition the integer number.
        integer :: z
        integer :: w
!
        if (a(z) == 0)a(z) = a(z-1)
        a(z) = a(z) + 1
        b(z) = p(a(z))
        return
    end subroutine getp

    subroutine part(num_found)
        integer, intent(in) :: num_found
        integer :: i, s, k, r
        logical :: bu
        a = 0
        do i = 1, num_found
            call getp(i)
        end do
   infinite: do
            sum_primes = 0
            bu = .false.
    nextin:do s = 1, num_found
                sum_primes = sum_primes + b(s)  !Adds the sth prime to sum_primes.
                if (sum_primes > number) then   !If the sum of primes exceeds number:
                    if (s == 1)then
                        exit infinite           !If only one prime has been added, exit the infinite loop.
                    endif
                    a(s:num_found) = 0          ! Resets the indices of the primes from s to num_found
                    do r = s - 1, num_found     ! Gets the next set of primes from s-1 to num_found
                        call getp(r)
                    end do
                    bu = .true.                 ! Sets bu to true and exits the loop over the primes
                    exit nextin
                end if
            end do nextin
            if (.not. bu) then                  ! If bu is false (meaning the sum of primes does not exceed number)
                if (sum_primes == number) exit infinite !We got it so go
                if (sum_primes < number) then
                    call getp(num_found)        ! If the sum of primes is less than number, gets the next prime
                else
                    error stop " Something wrong here!"
                endif
            endif
        end do infinite
        write( *,'(/,a,1x,i0,1x,a,1x,i0,1x,a)',advance='yes') "Partition", number, "into", num_found,trim(adjustl(list(num_found)))
    end subroutine part
!
    function list(num_found)
        integer, intent(in) :: num_found
        integer :: i
        character(len=128) :: list
        character(len = 10):: pooka
!
        write(list,'(i0)') b(1)
        if (sum_primes == number) then
            do i = 2, num_found
                pooka = ''
                write(pooka,'(i0)') b(i)
                list = trim(list) // " + " // adjustl(pooka)
            end do
        else
            list = "(not possible)"
        end if
        list = "primes: " // list
    end function list
    !
    subroutine eratosthenes(p , n)
      implicit none
!
! dummy arguments
!
      integer  ::  n
      logical*1 , dimension(0:*)  ::  p
      intent (in) n
      intent (inout) p
!
! local variables
!
      integer  ::  i
      integer  ::  ii
      logical  ::  oddeven
      integer  ::  pr
!
      p(0:n) = .false.
      p(1) = .false.
      p(2) = .true.
      oddeven = .true.
      do i = 3 , n,2
          p(i) = .true.
      end do
      do i = 2 , int(sqrt(float(n)))
         ii = i + i
         if( p(i) )then
            do pr = i*i , n , ii
               p(pr) = .false.
            end do
         end if
      end do
      return
      end subroutine eratosthenes

end module primes_module

program prime_partition
    use primes_module
    implicit none
    integer :: x, n,i
    integer :: xx,yy
    integer :: values(10,2)
! The given dataset from Rosetta Code
     !    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.
    values(1,:) = (/99809,1/)
    values(2,:) = (/18,2/)
    values(3,:) = (/19,3/)
    values(4,:) = (/20,4/)
    values(5,:) = (/2017,24/)
    values(6,:) = (/22699, 1/)
    values(7,:) = (/22699, 2/)
    values(8,:) = (/22699, 3/)
    values(9,:) = (/22699, 4/)
    values(10,:) = (/40355, 3/)
    i = maxval(values(1:10,1))*2
    call init(i)	! Set up a few basics
    call genp(i)	! Generate primes up to i
    do i = 1,10
        call setnum( values(i,1))
        call part(values(i,2))
    end do
    Stop 'Successfully completed'
end program prime_partition

Output:

Partition 99809 into 1 primes: 99809
Partition 18 into 2 primes   : 5 + 13
Partition 19 into 3 primes   : 3 + 5 + 11
Partition 20 into 4 primes   : (not possible)
Partition 2017 into 24 primes: 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 primes: 22699
Partition 22699 into 2 primes: 2 + 22697
Partition 22699 into 3 primes: 3 + 5 + 22691
Partition 22699 into 4 primes: 2 + 3 + 43 + 22651
Partition 40355 into 3 primes: 3 + 139 + 40213

Go

Translation of: Kotlin

... though uses a sieve to generate the relevant primes.

package main

import (
    "fmt"
    "log"
)

var (
    primes     = sieve(100000)
    foundCombo = false
)

func sieve(limit uint) []uint {
    primes := []uint{2}
    c := make([]bool, limit+1) // composite = true
    // no need to process even numbers > 2
    p := uint(3)
    for {
        p2 := p * p
        if p2 > limit {
            break
        }
        for i := p2; i <= limit; i += 2 * p {
            c[i] = true
        }
        for {
            p += 2
            if !c[p] {
                break
            }
        }
    }
    for i := uint(3); i <= limit; i += 2 {
        if !c[i] {
            primes = append(primes, i)
        }
    }
    return primes
}

func findCombo(k, x, m, n uint, combo []uint) {
    if k >= m {
        sum := uint(0)
        for _, c := range combo {
            sum += primes[c]
        }
        if sum == x {
            s := "s"
            if m == 1 {
                s = " "
            }
            fmt.Printf("Partitioned %5d with %2d prime%s: ", x, m, s)
            for i := uint(0); i < m; i++ {
                fmt.Print(primes[combo[i]])
                if i < m-1 {
                    fmt.Print("+")
                } else {
                    fmt.Println()
                }
            }
            foundCombo = true
        }
    } else {
        for j := uint(0); j < n; j++ {
            if k == 0 || j > combo[k-1] {
                combo[k] = j
                if !foundCombo {
                    findCombo(k+1, x, m, n, combo)
                }
            }
        }
    }
}

func partition(x, m uint) error {
    if !(x >= 2 && m >= 1 && m < x) {
        return fmt.Errorf("x must be at least 2 and m in [1, x)")
    }
    n := uint(0)
    for _, prime := range primes {
        if prime <= x {
            n++
        }
    }
    if n < m {
        return fmt.Errorf("not enough primes")
    }
    combo := make([]uint, m)
    foundCombo = false
    findCombo(0, x, m, n, combo)
    if !foundCombo {
        s := "s"
        if m == 1 {
            s = " "
        }
        fmt.Printf("Partitioned %5d with %2d prime%s: (impossible)\n", x, m, s)
    }
    return nil
}

func main() {
    a := [...][2]uint{
        {99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
        {22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3},
    }
    for _, p := range a {
        err := partition(p[0], p[1])
        if err != nil {
            log.Println(err)
        }
    }
}

Output:

Partitioned 99809 with  1 prime : 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: (impossible)
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime : 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

Haskell

import Data.List (delete, intercalate)
import Data.Numbers.Primes (primes)
import Data.Bool (bool)

-------------------- PRIME PARTITIONS ---------------------
partitions :: Int -> Int -> [Int]
partitions x n
  | n <= 1 =
    [ x
    | x == last ps ]
  | otherwise = go ps x n
  where
    ps = takeWhile (<= x) primes
    go ps_ x 1 =
      [ x
      | x `elem` ps_ ]
    go ps_ x n = ((flip bool [] . head) <*> null) (ps_ >>= found)
      where
        found p =
          ((flip bool [] . return . (p :)) <*> null)
            ((go =<< delete p . flip takeWhile ps_ . (>=)) (x - p) (pred n))

-------------------------- TEST ---------------------------
main :: IO ()
main =
  mapM_ putStrLn $
  (\(x, n) ->
      intercalate
        " -> "
        [ justifyLeft 9 ' ' (show (x, n))
        , let xs = partitions x n
          in bool
               (tail $ concatMap (('+' :) . show) xs)
               "(no solution)"
               (null xs)
        ]) <$>
  concat
    [ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]
    , (,) 22699 <$> [1 .. 4]
    , [(40355, 3)]
    ]

------------------------- GENERIC -------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)

Output:

(99809,1) -> 99809
(18,2)    -> 5+13
(19,3)    -> 3+5+11
(20,4)    -> (no solution)
(2017,24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
(22699,1) -> 22699
(22699,2) -> 2+22697
(22699,3) -> 3+5+22691
(22699,4) -> 2+3+43+22651
(40355,3) -> 3+139+40213

J

load 'format/printf'
 
NB. I don't know of any way to easily make an idiomatic lazy exploration, 
NB. except falling back on explicit imperative control strutures.
NB. However this is clearly not where J shines neither with speed nor elegance.
 
primes_up_to  =: monad def 'p: i. _1 p: 1 + y'
terms_as_text =: monad def '; }: , (": each y),.<'' + ''' 
 
search_next_terms =: dyad define
 acc=. x     NB. -> an accumulator that contains given beginning of the partition.
 p=.   >0{y  NB. -> number of elements wanted in the partition
 ns=.  >1{y  NB. -> candidate values to be included in the partition
 sum=. >2{y  NB. -> the integer to partition 
 
 if. p=0 do.
    if. sum=+/acc do. acc return. end.
 else.
   for_m. i. (#ns)-(p-1) do.
     r =. (acc,m{ns) search_next_terms (p-1);((m+1)}.ns);sum
     if. #r do. r return. end.
   end.
 end.
 
 0$0   NB. Empty result if nothing found at the end of this path.
)
 
 
NB. Prints  a partition of y primes whose sum equals x.
partitioned_in =: dyad define    
    terms =. (0$0) search_next_terms y;(primes_up_to x);x
    if. #terms do.
       'As the sum of %d primes, %d = %s' printf y;x; terms_as_text terms
    else.
       'Didn''t find a way to express %d as a sum of %d different primes.' printf x;y
    end.
)


tests=: (99809 1) ; (18 2) ; (19 3) ; (20 4) ; (2017 24) ; (22699 1) ; (22699 2) ; (22699 3) ; (22699 4)
(0&{ partitioned_in 1&{) each tests

Output:

As the sum of 1 primes, 99809 = 99809
As the sum of 2 primes, 18 = 5 + 13
As the sum of 3 primes, 19 = 3 + 5 + 11
Didn't find a way to express 20 as a sum of 4 different primes.
As the sum of 24 primes, 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
As the sum of 1 primes, 22699 = 22699
As the sum of 2 primes, 22699 = 2 + 22697
As the sum of 3 primes, 22699 = 3 + 5 + 22691
As the sum of 4 primes, 22699 = 2 + 3 + 43 + 22651
As the sum of 3 primes, 40355 = 3 + 139 + 40213

Java

Translation of: Kotlin

import java.util.Arrays;
import java.util.stream.IntStream;

public class PartitionInteger {
    private static final int[] primes = IntStream.concat(IntStream.of(2), IntStream.iterate(3, n -> n + 2))
        .filter(PartitionInteger::isPrime)
        .limit(50_000)
        .toArray();

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        if (n % 3 == 0) return n == 3;
        int d = 5;
        while (d * d <= n) {
            if (n % d == 0) return false;
            d += 2;
            if (n % d == 0) return false;
            d += 4;
        }
        return true;
    }

    private static boolean findCombo(int k, int x, int m, int n, int[] combo) {
        boolean foundCombo = false;
        if (k >= m) {
            if (Arrays.stream(combo).map(i -> primes[i]).sum() == x) {
                String s = m > 1 ? "s" : "";
                System.out.printf("Partitioned %5d with %2d prime%s: ", x, m, s);
                for (int i = 0; i < m; ++i) {
                    System.out.print(primes[combo[i]]);
                    if (i < m - 1) System.out.print('+');
                    else System.out.println();
                }
                foundCombo = true;
            }
        } else {
            for (int j = 0; j < n; ++j) {
                if (k == 0 || j > combo[k - 1]) {
                    combo[k] = j;
                    if (!foundCombo) {
                        foundCombo = findCombo(k + 1, x, m, n, combo);
                    }
                }
            }
        }
        return foundCombo;
    }

    private static void partition(int x, int m) {
        if (x < 2 || m < 1 || m >= x) {
            throw new IllegalArgumentException();
        }
        int[] filteredPrimes = Arrays.stream(primes).filter(it -> it <= x).toArray();
        int n = filteredPrimes.length;
        if (n < m) throw new IllegalArgumentException("Not enough primes");
        int[] combo = new int[m];
        boolean foundCombo = findCombo(0, x, m, n, combo);
        if (!foundCombo) {
            String s = m > 1 ? "s" : " ";
            System.out.printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, s);
        }
    }

    public static void main(String[] args) {
        partition(99809, 1);
        partition(18, 2);
        partition(19, 3);
        partition(20, 4);
        partition(2017, 24);
        partition(22699, 1);
        partition(22699, 2);
        partition(22699, 3);
        partition(22699, 4);
        partition(40355, 3);
    }
}

Output:

Partitioned 99809 with  1 prime: 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime: 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

jq

Works with jq and with gojq, the Go implementation of jq

Prime-number functions

 
# Is the input integer a prime?
def is_prime:
  if . == 2 then true
  else 2 < . and . % 2 == 1 and
       . as $in
       | (($in + 1) | sqrt) as $m
       | (((($m - 1) / 2) | floor) + 1) as $max
       | all( range(1; $max) ; $in % ((2 * .) + 1) > 0 )
  end;

# Is the input integer a prime?
# `previous` should be a sorted array of consecutive primes
# greater than 1 and at least including the greatest prime less than (.|sqrt)
def is_prime(previous):
  . as $in
  | (($in + 1) | sqrt) as $sqrt
  | first(previous[]
          | if . > $sqrt then 1
            elif 0 == ($in % .) then 0
            else empty
            end) // 1
  | . == 1;

# This assumes . is an array of consecutive primes beginning with [2,3]
def next_prime:
  . as $previous
  | (2 +  .[-1] ) 
  | until(is_prime($previous); . + 2) ;

# Emit primes from 2 up
def primes:
  # The helper function has arity 0 for TCO
  # It expects its input to be an array of previously found primes, in order:
  def next:
     . as $previous
     | ($previous|next_prime) as $next
     | $next, (($previous + [$next]) | next) ;
  2, 3, ([2,3] | next);

# The primes less than or equal to $x
def primes($x):
  label $out
  | primes | if . > $x then break $out else . end;

Helper function

# Emit a stream consisting of arrays, a, of $n items from the input array, 
# preserving order, subject to (a|add) == $sum
def take($n; $sum):
  def take:
    . as [$m, $in, $s]
    | if $m==0 and $s == 0 then []
      elif $m==0 or $s <= 0 then empty
      else range(0;$in|length) as $i
      | $in[$i] as $x
      | if $x > $s then empty
        else [$x] + ([$m-1, $in[$i+1:], $s - $x] | take)
        end
      end;
  [$n, ., $sum] | take;

Partitioning an integer into $n primes

# This function emits a possibly empty stream of arrays.
# Assuming $primes is primes(.), each array corresponds to a
# partition of the input into $n distinct primes.
# The algorithm is unoptimized.
# The output is a stream of arrays, which would be empty
def primepartition($n; $primes):
  . as $x
  | if $n == 1
    then if $primes[-1] == $x then [$x] else null end
    else (if $primes[-1] == $x then $primes[:-1] else $primes end) as $primes
    | ($primes | take($n; $x)) 
    end ;

# See primepartition/2
def primepartition($n):
  . as $x
  | if $n == 1
    then if is_prime then [.] else null end
    else primepartition($n; [primes($x)])
    end;

# Compute first(primepartition($n)) for each $n in the array $ary
def primepartitions($ary):
  . as $x
  | [primes($x)] as $px
  | $ary[] as $n
  | $x
  | first(primepartition($n; $px));

def task($x; $n):
  def pp:
    if . then join("+") else "(not possible)" end;

  if $n|type == "array" then task($x; $n[])
  else "A partition of \($x) into \($n) parts: \(first($x | primepartition($n)) | pp )"
  end;

The tasks

task(18; 2),
task(19; 3),
task(20; 4),
task(2017; 24),
task(22699; [1,2,3,4]),
task(40355; 3)

Output:

A partition of 18 into 2 parts: 5+13
A partition of 19 into 3 parts: 3+5+11
A partition of 2017 into 24 parts: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
A partition of 22699 into 1 parts: 22699
A partition of 22699 into 2 parts: 2+22697
A partition of 22699 into 3 parts: 3+5+22691
A partition of 22699 into 4 parts: 2+3+43+22651
A partition of 40355 into 3 parts: 3+139+40213

Julia

Translation of: Sidef

using Primes, Combinatorics

function primepartition(x::Int64, n::Int64)
    if n == oftype(n, 1)
        return isprime(x) ? [x] : Int64[]
    else
        for combo in combinations(primes(x), n)
            if sum(combo) == x
                return combo
            end
        end
    end
    return Int64[]
end

for (x, n) in [[   18, 2], [   19, 3], [   20,  4], [99807, 1], [99809, 1],
         [ 2017, 24],[22699, 1], [22699, 2], [22699,  3], [22699, 4] ,[40355, 3]]
    ans = primepartition(x, n)
    println("Partition of ", x, " into ", n, " primes: ",
        isempty(ans) ? "impossible" : join(ans, " + "))
end

Output:

Partition of 18 into 2 prime pieces: 5 + 13
Partition of 19 into 3 prime pieces: 3 + 5 + 11
Partition of 20 into 4 prime pieces: impossible
Partition of 99807 into 1 prime piece: impossible
Partition of 99809 into 1 prime piece: 99809
Partition of 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 of 22699 into 1 prime piece: 22699
Partition of 22699 into 2 prime pieces: 2 + 22697
Partition of 22699 into 3 prime pieces: 3 + 5 + 22691
Partition of 22699 into 4 prime pieces: 2 + 3 + 43 + 22651
Partition of 40355 into 3 prime pieces: 3 + 139 + 40213

Kotlin

// version 1.1.2

// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning
 
import kotlin.coroutines.experimental.* 

val primes = generatePrimes().take(50_000).toList()  // generate first 50,000 say
var foundCombo = false
 
fun isPrime(n: Int) : Boolean {
    if (n < 2) return false 
    if (n % 2 == 0) return n == 2
    if (n % 3 == 0) return n == 3
    var d : Int = 5
    while (d * d <= n) {
        if (n % d == 0) return false
        d += 2
        if (n % d == 0) return false
        d += 4
    }
    return true
}
 
fun generatePrimes() =
    buildSequence {
        yield(2)
        var p = 3
        while (p <= Int.MAX_VALUE) { 
           if (isPrime(p)) yield(p)
           p += 2
        }
    }

fun findCombo(k: Int, x: Int, m: Int, n: Int, combo: IntArray) {
    if (k >= m) {
        if (combo.sumBy { primes[it] } == x) {
           val s = if (m > 1) "s" else " "
           print("Partitioned ${"%5d".format(x)} with ${"%2d".format(m)} prime$s: ")
           for (i in 0 until m) {
               print(primes[combo[i]])
               if (i < m - 1) print("+") else println()
           } 
           foundCombo = true
        }            
    }
    else { 
        for (j in 0 until n) {
            if (k == 0 || j > combo[k - 1]) {
                combo[k] = j
                if (!foundCombo) findCombo(k + 1, x, m, n, combo)
            }
        }
    }
}

fun partition(x: Int, m: Int) {
    require(x >= 2 && m >= 1 && m < x)
    val filteredPrimes = primes.filter { it <= x }
    val n = filteredPrimes.size
    if (n < m) throw IllegalArgumentException("Not enough primes")
    val combo = IntArray(m)
    foundCombo = false
    findCombo(0, x, m, n, combo)   
    if (!foundCombo) {
        val s = if (m > 1) "s" else " "   
        println("Partitioned ${"%5d".format(x)} with ${"%2d".format(m)} prime$s: (not possible)")
    }
}
    
fun main(args: Array<String>) {
    val a = arrayOf(
        99809 to 1,
        18 to 2,
        19 to 3,
        20 to 4,
        2017 to 24,
        22699 to 1,
        22699 to 2,
        22699 to 3,
        22699 to 4,
        40355 to 3
    )
    for (p in a) partition(p.first, p.second)    
}

Output:

Partitioned 99809 with  1 prime : 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime : 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

Lingo

Using the prime generator class "sieve" from task Extensible prime generator#Lingo.

----------------------------------------
-- 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

-- main
_global.sieve = script("sieve").new()

showPrimePartition(99809, 1)
showPrimePartition(18, 2)
showPrimePartition(19, 3)
showPrimePartition(20, 4)
showPrimePartition(2017, 24)
showPrimePartition(22699, 1)
showPrimePartition(22699, 2)
showPrimePartition(22699, 3)
showPrimePartition(22699, 4)
showPrimePartition(40355, 3)

Output:

-- "Partitioned 99809 with 1 primes: 99809"
-- "Partitioned 18 with 2 primes: 5+13"
-- "Partitioned 19 with 3 primes: 3+5+11"
-- "Partitioned 20 with 4 primes: not prossible"
-- "Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129"
-- "Partitioned 22699 with 1 primes: 22699"
-- "Partitioned 22699 with 2 primes: 2+22697"
-- "Partitioned 22699 with 3 primes: 3+5+22691"
-- "Partitioned 22699 with 4 primes: 2+3+43+22651"
-- "Partitioned 40355 with 3 primes: 3+139+40213"

Mathematica/Wolfram Language

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

Output:

0.111699	Partitioned 99809 with 1 prime: 99809
0.000407	Partitioned 18 with 2 primes: 5+13
0.000346	Partitioned 19 with 3 primes: 3+5+11
0.000765	Partitioned 20 with 4 primes: no solutions found
0.008381	Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
0.028422	Partitioned 22699 with 1 prime: 22699
0.02713		Partitioned 22699 with 2 primes: 2+22697
20.207		Partitioned 22699 with 3 primes: 3+5+22691
0.357536	Partitioned 22699 with 4 primes: 2+3+43+22651
57.9928		Partitioned 40355 with 3 primes: 3+139+40213

Nim

import math, sugar

const N = 100_000

# Fill a sieve of Erathostenes.
var isPrime {.noInit.}: array[2..N, bool]
for item in isPrime.mitems: item = true
for n in 2..int(sqrt(N.toFloat)):
  if isPrime[n]:
    for k in countup(n * n, N, n):
      isPrime[k] = false

# Build list of primes.
let primes = collect(newSeq):
               for n in 2..N:
                 if isPrime[n]: n


proc partition(n, k: int; start = 0): seq[int] =
  ## Partition "n" in "k" primes starting at position "start" in "primes".
  ## Return the list of primes or an empty list if partitionning is impossible.

  if k == 1:
    return if isPrime[n] and n >= primes[start]: @[n] else: @[]

  for i in start..primes.high:
    let a = primes[i]
    if n - a <= 1: break
    result = partition(n - a, k - 1, i + 1)
    if result.len != 0:
      return a & result


when isMainModule:

  import strutils

  func plural(k: int): string =
    if k <= 1: "" else: "s"

  for (n, k) in [(99809, 1), (18, 2), (19, 3), (20, 4),
                (2017, 24), (22699, 1), (22699, 2),
                (22699, 3), (22699, 4), (40355, 3)]:
    let part = partition(n, k)
    if part.len == 0:
      echo n, " cannot be partitionned into ", k, " prime", plural(k)
    else:
      echo n, " = ", part.join(" + ")

Output:

99809 = 99809
18 = 5 + 13
19 = 3 + 5 + 11
20 cannot be partitionned into 4 primes
2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
22699 = 22699
22699 = 2 + 22697
22699 = 3 + 5 + 22691
22699 = 2 + 3 + 43 + 22651
40355 = 3 + 139 + 40213

PARI/GP

partDistinctPrimes(x,n,mn=2)=
{
  if(n==1, return(if(isprime(x) && mn<=x, [x], 0)));
  if((x-n)%2,
    if(mn>2, return(0));
    my(t=partDistinctPrimes(x-2,n-1,3));
    return(if(t, concat(2,t), 0))
  );
  if(n==2,
    forprime(p=mn,(x-1)\2,
      if(isprime(x-p), return([p,x-p]))
    );
    return(0)
  );
  if(n<1, return(if(n, 0, [])));

  \\ x is the sum of 3 or more odd primes
  my(t);
  forprime(p=mn,(x-1)\n,
    t=partDistinctPrimes(x-p,n-1,p+2);
    if(t, return(concat(p,t)))
  );
  0;
}
displayNicely(x,n)=
{
  printf("Partitioned%6d with%3d prime", x, n);
  if(n!=1, print1("s"));
  my(t=partDistinctPrimes(x,n));
  if(t===0, print(": (not possible)"); return);
  if(#t, print1(": "t[1]));
  for(i=2,#t, print1("+"t[i]));
  print();
}
V=[[99809,1], [18,2], [19,3], [20,4], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
for(i=1,#V, call(displayNicely, V[i]))

Output:

Partitioned 99809 with  1 prime: 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime: 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

Perl

It is tempting to use the partition iterator which takes a "isprime" flag, but this task calls for unique values. Hence the combination iterator over an array of primes makes more sense.

Library: ntheory

use ntheory ":all";

sub prime_partition {
  my($num, $parts) = @_;
  return is_prime($num) ? [$num] : undef if $parts == 1;
  my @p = @{primes($num)};
  my $r;
  forcomb { lastfor, $r = [@p[@_]] if vecsum(@p[@_]) == $num; } @p, $parts;
  $r;
}

foreach my $test ([18,2], [19,3], [20,4], [99807,1], [99809,1], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]) {
  my $partar = prime_partition(@$test);
  printf "Partition %5d into %2d prime piece%s %s\n", $test->[0], $test->[1], ($test->[1] == 1) ? ": " : "s:", defined($partar) ? join("+",@$partar) : "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  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

Phix

with javascript_semantics
requires("1.0.2") -- (join(fmt))
function partition(integer v, n, idx=0)
    if n=1 then
        return iff(is_prime(v)?{v}:0)
    end if
    while true do
        idx += 1
        integer np = get_prime(idx)
        if np>=floor(v/2) then exit end if
        object res = partition(v-np, n-1, idx)
        if sequence(res) then
            res = prepend(res,np)
            return res
        end if
    end while
    return 0
end function
 
constant tests = {{99809, 1},
                  {18, 2},
                  {19, 3},
                  {20, 4},
                  {2017, 24},
                  {22699, 1},
                  {22699, 2},
                  {22699, 3},
                  {22699, 4},
                  {40355, 3}}
 
for i=1 to length(tests) do
    integer {v,n} = tests[i]
    object res = partition(v,n)
    res = iff(res=0?"not possible":join(res," + ",fmt:="%d"))
    printf(1,"Partition %d into %d primes: %s\n",{v,n,res})
end for

Output:

Partition 99809 into 1 primes: 99809
Partition 18 into 2 primes: 5 + 13
Partition 19 into 3 primes: 3 + 5 + 11
Partition 20 into 4 primes: not possible
Partition 2017 into 24 primes: 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 primes: 22699
Partition 22699 into 2 primes: 2 + 22697
Partition 22699 into 3 primes: 3 + 5 + 22691
Partition 22699 into 4 primes: 2 + 3 + 43 + 22651
Partition 40355 into 3 primes: 3 + 139 + 40213

Prolog

Works with: SWI Prolog

prime_partition(N, 1, [N], Min):-
    is_prime(N),
    N > Min,
    !.
prime_partition(N, K, [P|Rest], Min):-
    K > 1,
    is_prime(P),
    P > Min,
    P < N,
    K1 is K - 1,
    N1 is N - P,
    prime_partition(N1, K1, Rest, P),
    !.

prime_partition(N, K, Primes):-
    prime_partition(N, K, Primes, 1).

print_primes([Prime]):-
    !,
    writef('%w\n', [Prime]).
print_primes([Prime|Primes]):-
    writef('%w + ', [Prime]),
    print_primes(Primes).

print_prime_partition(N, K):-
    prime_partition(N, K, Primes),
    !,
    writef('%w = ', [N]),
    print_primes(Primes).
print_prime_partition(N, K):-
    writef('%w cannot be partitioned into %w primes.\n', [N, K]).

main:-
    find_prime_numbers(100000),
    print_prime_partition(99809, 1),
    print_prime_partition(18, 2),
    print_prime_partition(19, 3),
    print_prime_partition(20, 4),
    print_prime_partition(2017, 24),
    print_prime_partition(22699, 1),
    print_prime_partition(22699, 2),
    print_prime_partition(22699, 3),
    print_prime_partition(22699, 4),
    print_prime_partition(40355, 3).

Module for finding prime numbers up to some limit:

:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.

find_prime_numbers(N):-
    retractall(is_prime(_)),
    assertz(is_prime(2)),
    init_sieve(N, 3),
    sieve(N, 3).

init_sieve(N, P):-
    P > N,
    !.
init_sieve(N, P):-
    assertz(is_prime(P)),
    Q is P + 2,
    init_sieve(N, Q).

sieve(N, P):-
    P * P > N,
    !.
sieve(N, P):-
    is_prime(P),
    !,
    S is P * P,
    cross_out(S, N, P),
    Q is P + 2,
    sieve(N, Q).
sieve(N, P):-
    Q is P + 2,
    sieve(N, Q).

cross_out(S, N, _):-
    S > N,
    !.
cross_out(S, N, P):-
    retract(is_prime(S)),
    !,
    Q is S + 2 * P,
    cross_out(Q, N, P).
cross_out(S, N, P):-
    Q is S + 2 * P,
    cross_out(Q, N, P).

Output:

99809 = 99809
18 = 5 + 13
19 = 3 + 5 + 11
20 cannot be partitioned into 4 primes.
2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
22699 = 22699
22699 = 2 + 22697
22699 = 3 + 5 + 22691
22699 = 2 + 3 + 43 + 22651
40355 = 3 + 139 + 40213

Python

from itertools import combinations as cmb


def isP(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    return all(n % x > 0 for x in range(3, int(n ** 0.5) + 1, 2))


def genP(n):
    p = [2]
    p.extend([x for x in range(3, n + 1, 2) if isP(x)])
    return p


data = [
    (99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
    (22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)]


for n, cnt in data:
    ci = iter(cmb(genP(n), cnt))
    while True:
        try:
            c = next(ci)
            if sum(c) == n:
                print(' '.join(
                    [repr((n, cnt)), "->", '+'.join(str(s) for s in c)]
                ))
                break
        except StopIteration:
            print(repr((n, cnt)) + " -> Not possible")
            break

Output:

(99809, 1) -> 99809
(18, 2) -> 5+13
(19, 3) -> 3+5+11
(20, 4) -> Not possible
(2017, 24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
(22699, 1) -> 22699
(22699, 2) -> 2+22697
(22699, 3) -> 3+5+22691
(22699, 4) -> 2+3+43+22651
(40355, 3) -> 3+139+40213

Racket

#lang racket
(require math/number-theory)

(define memoised-next-prime
  (let ((m# (make-hash)))
    (λ (P) (hash-ref! m# P (λ () (next-prime P))))))

(define (partition-X-into-N-primes X N)
  (define (partition-x-into-n-primes-starting-at-P x n P result)
    (cond ((= n x 0) result)
          ((or (= n 0) (= x 0) (> P x)) #f)
          (else
           (let ((P′ (memoised-next-prime P)))
             (or (partition-x-into-n-primes-starting-at-P (- x P) (- n 1) P′ (cons P result))
                 (partition-x-into-n-primes-starting-at-P x n P′ result))))))
  
  (reverse (or (partition-x-into-n-primes-starting-at-P X N 2 null) (list 'no-solution))))

(define (report-partition X N)
  (let ((result (partition-X-into-N-primes X N)))
    (printf "partition ~a\twith ~a\tprimes: ~a~%" X N (string-join (map ~a result) " + "))))

(module+ test
  (report-partition 99809 1)
  (report-partition 18 2)
  (report-partition 19 3)
  (report-partition 20 4)
  (report-partition 2017 24)
  (report-partition 22699 1)
  (report-partition 22699 2)
  (report-partition 22699 3)
  (report-partition 22699 4)
  (report-partition 40355 3))

Output:

partition 99809	with 1	primes: 99809
partition 18	with 2	primes: 5 + 13
partition 19	with 3	primes: 3 + 5 + 11
partition 20	with 4	primes: no-solution
partition 2017	with 24	primes: 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	with 1	primes: 22699
partition 22699	with 2	primes: 2 + 22697
partition 22699	with 3	primes: 3 + 5 + 22691
partition 22699	with 4	primes: 2 + 3 + 43 + 22651
partition 40355	with 3	primes: 3 + 139 + 40213

Raku

(formerly Perl 6)

Works with: Rakudo version 2018.10

use Math::Primesieve;
my $sieve = Math::Primesieve.new;

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

multi partition ( Int $number, Int $parts where * > 0 = 2 ) {
    my @these = $sieve.primes($number);
    for @these.combinations($parts) { .return if .sum == $number };
    ()
}

# TESTING
(18,2, 19,3, 20,4, 99807,1, 99809,1, 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  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

Refal

$ENTRY Go {
    = <Each Test <Tests>>;
};

Tests {
    = (99809 1) (18 2) (19 3) (20 4) (2017 24)
      (22699 1) (22699 2) (22699 3) (22699 4) (40355 3);
};

Test {
    (s.X s.N) =
        <Prout 'Partitioned ' <Symb s.X> ' with ' <Symb s.N> ' primes: '
               <Format <PrimePartition s.X s.N>>>;
};

Format {
    F = 'not possible';
    T s.N = <Symb s.N>;
    T s.N e.X = <Symb s.N> '+' <Format T e.X>;
};

PrimePartition {
    s.X s.N = <Partition s.X s.N <Primes s.X>>;
};

Partition {
    s.X 1 e.Nums, e.Nums: {
        e.1 s.X e.2 = T s.X;
        e.1 = F;
    };
    s.X s.N = F;
    s.X s.N s.Num e.Nums, <Compare s.X s.Num>: '-' =
        <Partition s.X s.N e.Nums>;
    s.X s.N s.Num e.Nums,
        <Partition <- s.X s.Num> <- s.N 1> e.Nums>: {
            T e.List = T s.Num e.List;
            F = <Partition s.X s.N e.Nums>;
        };
};

Primes {
    s.N = <Sieve <Iota 2 s.N>>;
};

Iota {
    s.End s.End = s.End;
    s.Start s.End = s.Start <Iota <+ 1 s.Start> s.End>;
};

Cross {
    s.Step e.List = <Cross (s.Step 1) s.Step e.List>;
    (s.Step s.Skip) = ;
    (s.Step 1) s.Item e.List = X <Cross (s.Step s.Step) e.List>;
    (s.Step s.N) s.Item e.List = s.Item <Cross (s.Step <- s.N 1>) e.List>;
};

Sieve {
    = ;
    X e.List = <Sieve e.List>;
    s.N e.List = s.N <Sieve <Cross s.N e.List>>;
};

Each {
    s.F = ;
    s.F t.X e.R = <Mu s.F t.X> <Each s.F e.R>;
};

Output:

Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213

REXX

Usage note:   entering ranges of   X   and   N   numbers (arguments) from the command line:

  X-Y   N-M     ∙∙∙

which means:   partition all integers (inclusive) from   X ──► Y   with   N ──► M   primes.
The   to   number   (Y   or   M)   can be omitted.

/*REXX program  partitions  integer(s)    (greater than unity)   into   N   primes.     */
parse arg what                                   /*obtain an optional list from the C.L.*/

  do  until what==''                             /*possibly process a series of integers*/
  parse var what x n what; parse var  x  x '-' y /*get possible range  and # partitions.*/
                           parse var  n  n '-' m /* "      "      "     "  "      "     */
  if x=='' | x==","   then x= 19                 /*Not specified?  Then use the default.*/
  if y=='' | y==","   then y=  x                 /* "      "         "   "   "     "    */
  if n=='' | n==","   then n=  3                 /* "      "         "   "   "     "    */
  if m=='' | m==","   then m=  n                 /* "      "         "   "   "     "    */
  call genP y                                    /*generate   Y   number of primes.     */
                     do   g=x  to y              /*partition  X ───► Y  into partitions.*/
                       do q=n  to m;  call part  /*    "      G   into    Q    primes.  */
                       end  /*q*/
                     end    /*g*/
  end   /*until*/

exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: arg high;     @.1= 2;   @.2= 3;    #= 2    /*get highest prime, assign some vars. */
               do j=@.#+2  by 2  until @.#>high  /*only find odd primes from here on.   */
                  do k=2  while k*k<=j           /*divide by some known low odd primes. */
                  if j // @.k==0  then iterate j /*Is  J  divisible by P?  Then ¬ prime.*/
                  end   /*k*/                    /* [↓]  a prime  (J)  has been found.  */
               #= # + 1;               @.#= j    /*bump prime count; assign prime to  @.*/
               end      /*j*/;         return
/*──────────────────────────────────────────────────────────────────────────────────────*/
getP: procedure expose i. p. @.;  parse arg z    /*bump the prime in the partition list.*/
      if i.z==0  then do;   _= z - 1;     i.z= i._;   end
      i.z= i.z + 1;         _= i.z;       p.z= @._;                      return 0
/*──────────────────────────────────────────────────────────────────────────────────────*/
list: _= p.1;    if $==g  then do j=2  to q;     _= _ p.j
                               end   /*j*/
                          else _= '__(not_possible)'
      return 'prime'  ||  word("s", 1 + (q==1))   translate(_, '+ ', " _")    /*plural? */
/*──────────────────────────────────────────────────────────────────────────────────────*/
part: i.= 0;  do j=1  for q;   call getP j
              end   /*j*/

              do !=0  by 0;         $= 0         /*!:  a DO variable for LEAVE & ITERATE*/
                  do s=1  for q;    $= $ + p.s   /* [↓]  is sum of the primes too large?*/
                  if $>g  then do;  if s==1  then leave !        /*perform a quick exit?*/
                                         do k=s    to q;  i.k= 0;       end  /*k*/
                                         do r=s-1  to q;  call getP r;  end  /*r*/
                                    iterate !
                               end
                  end   /*s*/
              if $==g  then leave                /*is sum of the primes exactly right ? */
              if $ <g  then do;    call getP q;    iterate;    end
              end   /*!*/                        /* [↑]   Is sum too low?  Bump a prime.*/
      say 'partitioned'       center(g,9)        "into"        center(q, 5)        list()
      return

output   when using the input of:   99809 1   18 2   19 3  20 4   2017 24   22699 1-4   40355

partitioned   99809   into   1   prime:  99809
partitioned    18     into   2   primes: 5+13
partitioned    19     into   3   primes: 3+5+11
partitioned    20     into   4   primes:   (not possible)
partitioned   2017    into  24   primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
partitioned   22699   into   1   prime:  22699
partitioned   22699   into   2   primes: 2+22697
partitioned   22699   into   3   primes: 3+5+22691
partitioned   22699   into   4   primes: 2+3+43+22651
partitioned   40355   into   3   primes: 3+139+40213

Ring

# Project : Partition an integer X into N primes

load "stdlib.ring"
nr = 0
num = 0
list = list(100000)
items = newlist(pow(2,len(list))-1,100000)
while true
          nr = nr + 1
          if isprime(nr)
             num = num + 1
             list[num] = nr
          ok
          if num = 100000
              exit
          ok
end

powerset(list,100000)
showarray(items,100000)
see nl

func showarray(items,ind)
        for p = 1 to 20
              if (p > 17 and p < 21) or p = 99809 or p = 2017  or p = 22699  or p = 40355  
                  for n = 1 to len(items)
                       flag = 0
                       for m = 1 to ind
                             if items[n][m] = 0 
                                exit
                             ok   
                             flag = flag + items[n][m]
                       next
                       if flag = p
                          str = ""
                          for x = 1 to len(items[n])
                               if items[n][x] != 0  
                                  str = str + items[n][x] + " "
                               ok
                          next  
                          str = left(str, len(str) - 1) 
                          str = str + "]"
                          if substr(str, " ") > 0
                             see "" + p + " = [" 
                             see str + nl
                             exit
                          else
                             str = ""
                          ok
                       ok
                  next
              ok
        next

func powerset(list,ind)
        num = 0
        num2 = 0
        items = newlist(pow(2,len(list))-1,ind)
        for i = 2 to (2 << len(list)) - 1 step 2
             num2 = 0
             num = num + 1
             for j = 1 to len(list) 
                  if i & (1 << j)
                      num2 = num2 + 1
                      if list[j] != 0
                        items[num][num2] = list[j]
                     ok
                  ok
             next
        next
        return items

Output:

99809 = [99809]
18 = [5 13]
19 = [3 5 11]
20 = []
2017 = [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 97 1129]
22699 = [22699]
22699 = [2 22697]
22699 = [3 5 22691]
22699 = [2 3 43 22651]
40355 = [3 139 40213]

Ruby

require "prime"

def prime_partition(x, n)
  Prime.each(x).to_a.combination(n).detect{|primes| primes.sum == x}
end

TESTCASES = [[99809, 1], [18, 2], [19, 3], [20, 4], [2017, 24], 
             [22699, 1], [22699, 2], [22699, 3], [22699, 4], [40355, 3]]

TESTCASES.each do |prime, num|
  res = prime_partition(prime, num) 
  str = res.nil? ? "no solution" : res.join(" + ")
  puts  "Partitioned #{prime} with #{num} primes: #{str}"
end

Output:

Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5 + 13
Partitioned 19 with 3 primes: 3 + 5 + 11
Partitioned 20 with 4 primes: no solution
Partitioned 2017 with 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2 + 22697
Partitioned 22699 with 3 primes: 3 + 5 + 22691
Partitioned 22699 with 4 primes: 2 + 3 + 43 + 22651
Partitioned 40355 with 3 primes: 3 + 139 + 40213

Rust

Translation of: C

// main.rs
mod bit_array;
mod prime_sieve;

use prime_sieve::PrimeSieve;

fn find_prime_partition(
    sieve: &PrimeSieve,
    number: usize,
    count: usize,
    min_prime: usize,
    primes: &mut Vec<usize>,
    index: usize,
) -> bool {
    if count == 1 {
        if number >= min_prime && sieve.is_prime(number) {
            primes[index] = number;
            return true;
        }
        return false;
    }
    for p in min_prime..number {
        if sieve.is_prime(p)
            && find_prime_partition(sieve, number - p, count - 1, p + 1, primes, index + 1)
        {
            primes[index] = p;
            return true;
        }
    }
    false
}

fn print_prime_partition(sieve: &PrimeSieve, number: usize, count: usize) {
    let mut primes = vec![0; count];
    if !find_prime_partition(sieve, number, count, 2, &mut primes, 0) {
        println!("{} cannot be partitioned into {} primes.", number, count);
    } else {
        print!("{} = {}", number, primes[0]);
        for i in 1..count {
            print!(" + {}", primes[i]);
        }
        println!();
    }
}

fn main() {
    let s = PrimeSieve::new(100000);
    print_prime_partition(&s, 99809, 1);
    print_prime_partition(&s, 18, 2);
    print_prime_partition(&s, 19, 3);
    print_prime_partition(&s, 20, 4);
    print_prime_partition(&s, 2017, 24);
    print_prime_partition(&s, 22699, 1);
    print_prime_partition(&s, 22699, 2);
    print_prime_partition(&s, 22699, 3);
    print_prime_partition(&s, 22699, 4);
    print_prime_partition(&s, 40355, 3);
}

// prime_sieve.rs
use crate::bit_array;

pub struct PrimeSieve {
    composite: bit_array::BitArray,
}

impl PrimeSieve {
    pub fn new(limit: usize) -> PrimeSieve {
        let mut sieve = PrimeSieve {
            composite: bit_array::BitArray::new(limit / 2),
        };
        let mut p = 3;
        while p * p <= limit {
            if !sieve.composite.get(p / 2 - 1) {
                let inc = p * 2;
                let mut q = p * p;
                while q <= limit {
                    sieve.composite.set(q / 2 - 1, true);
                    q += inc;
                }
            }
            p += 2;
        }
        sieve
    }
    pub fn is_prime(&self, n: usize) -> bool {
        if n < 2 {
            return false;
        }
        if n % 2 == 0 {
            return n == 2;
        }
        !self.composite.get(n / 2 - 1)
    }
}

// bit_array.rs
pub struct BitArray {
    array: Vec<u32>,
}

impl BitArray {
    pub fn new(size: usize) -> BitArray {
        BitArray {
            array: vec![0; (size + 31) / 32],
        }
    }
    pub fn get(&self, index: usize) -> bool {
        let bit = 1 << (index & 31);
        (self.array[index >> 5] & bit) != 0
    }
    pub fn set(&mut self, index: usize, new_val: bool) {
        let bit = 1 << (index & 31);
        if new_val {
            self.array[index >> 5] |= bit;
        } else {
            self.array[index >> 5] &= !bit;
        }
    }
}

Output:

99809 = 99809
18 = 5 + 13
19 = 3 + 5 + 11
20 cannot be partitioned into 4 primes.
2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
22699 = 22699
22699 = 2 + 22697
22699 = 3 + 5 + 22691
22699 = 2 + 3 + 43 + 22651
40355 = 3 + 139 + 40213

Scala

object PartitionInteger {

  def sieve(nums: LazyList[Int]): LazyList[Int] =
    LazyList.cons(nums.head, sieve((nums.tail) filter (_ % nums.head != 0)))

  // An 'infinite' stream of primes, lazy evaluation and memo-ized
  private val oddPrimes = sieve(LazyList.from(3, 2))
  private val primes = sieve(2 #:: oddPrimes).take(3600 /*50_000*/)

  private def findCombo(k: Int, x: Int, m: Int, n: Int, combo: Array[Int]): Boolean = {
    var foundCombo = combo.map(i => primes(i)).sum == x
    if (k >= m) {
      if (foundCombo) {
        val s: String = if (m > 1) "s" else ""
        printf("Partitioned %5d with %2d prime%s: ", x, m, s)
        for (i <- 0 until m) {
          print(primes(combo(i)))
          if (i < m - 1) print('+') else println()
        }
      }
    } else for (j <- 0 until n if k == 0 || j > combo(k - 1)) {
      combo(k) = j
      if (!foundCombo) foundCombo = findCombo(k + 1, x, m, n, combo)
    }
    foundCombo
  }

  private def partition(x: Int, m: Int): Unit = {
    val n: Int = primes.count(it => it <= x)
    if (n < m) throw new IllegalArgumentException("Not enough primes")

    if (!findCombo(0, x, m, n, new Array[Int](m)))
      printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, if (m > 1) "s" else " ")
  }

  def main(args: Array[String]): Unit = {
    partition(99809, 1)
    partition(18, 2)
    partition(19, 3)
    partition(20, 4)
    partition(2017, 24)
    partition(22699, 1)
    partition(22699, 2)
    partition(22699, 3)
    partition(22699, 4)
    partition(40355, 3)
  }

}

SETL

program primes_partition;
    tests := [[99809,1], [18,2], [19,3], [20,4], [2017,24],
              [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];

    loop for [x, n] in tests do
        nprint("Partitioned",x,"with",n,"primes:");
        if (p := partition(x,n)) = om then
            print(" not possible");
        else
            print(" " + (+/["+" + str pr : pr in p])(2..));
        end if;
    end loop;

    proc partition(x,n);
        return findpart(x,n,sieve(x));
    end proc;

    proc findpart(x,n,nums);
        if n=1 then
            return if x in nums then [x] else om end;
        end if;

        loop while nums /= [] do
            k fromb nums;
            if (l := findpart(x-k, n-1, nums)) /= om then
                return [k] + l;
            end if;
        end loop;
        return om;
    end proc;

    proc sieve(n);
        primes := [1..n];
        primes(1) := om;
        loop for p in [2..floor sqrt n] do
            loop for c in [p*p, p*p+p..n] do
                primes(c) := om;
            end loop;
        end loop;
        return [p : p in primes | p /= om];
    end proc;
end program;

Output:

Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213

Sidef

Translation of: Perl

func prime_partition(num, parts) {

    if (parts == 1) {
        return (num.is_prime ? [num] : [])
    }

    num.primes.combinations(parts, {|*c|
        return c if (c.sum == num)
    })

    return []
}

var tests = [
    [   18, 2], [   19, 3], [   20,  4],
    [99807, 1], [99809, 1], [ 2017, 24],
    [22699, 1], [22699, 2], [22699,  3],
    [22699, 4], [40355, 3],
]

for num,parts (tests) {
    say ("Partition %5d into %2d prime piece" % (num, parts),
    parts == 1 ? ':  ' : 's: ', prime_partition(num, parts).join('+') || '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  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

Swift

Translation of: Rust

import Foundation

class BitArray {
    var array: [UInt32]

    init(size: Int) {
        array = Array(repeating: 0, count: (size + 31)/32)
    }
    
    func get(index: Int) -> Bool {
        let bit = UInt32(1) << (index & 31)
        return (array[index >> 5] & bit) != 0
    }
    
    func set(index: Int, value: Bool) {
        let bit = UInt32(1) << (index & 31)
        if value {
            array[index >> 5] |= bit
        } else {
            array[index >> 5] &= ~bit
        }
    }
}

class PrimeSieve {
    let composite: BitArray
    
    init(size: Int) {
        composite = BitArray(size: size/2)
        var p = 3
        while p * p <= size {
            if !composite.get(index: p/2 - 1) {
                let inc = p * 2
                var q = p * p
                while q <= size {
                    composite.set(index: q/2 - 1, value: true)
                    q += inc
                }
            }
            p += 2
        }
    }
    
    func isPrime(number: Int) -> Bool {
        if number < 2 {
            return false
        }
        if (number & 1) == 0 {
            return number == 2
        }
        return !composite.get(index: number/2 - 1)
    }
}

func findPrimePartition(sieve: PrimeSieve, number: Int,
                        count: Int, minPrime: Int,
                        primes: inout [Int], index: Int) -> Bool {
    if count == 1 {
        if number >= minPrime && sieve.isPrime(number: number) {
            primes[index] = number
            return true
        }
        return false
    }
    if minPrime >= number {
        return false
    }
    for p in minPrime..<number {
        if sieve.isPrime(number: p)
            && findPrimePartition(sieve: sieve, number: number - p,
                                  count: count - 1, minPrime: p + 1,
                                  primes: &primes, index: index + 1) {
            primes[index] = p
            return true
        }
    }
    return false
}

func printPrimePartition(sieve: PrimeSieve, number: Int, count: Int) {
    var primes = Array(repeating: 0, count: count)
    if !findPrimePartition(sieve: sieve, number: number, count: count,
                           minPrime: 2, primes: &primes, index: 0) {
        print("\(number) cannot be partitioned into \(count) primes.")
    } else {
        print("\(number) = \(primes[0])", terminator: "")
        for i in 1..<count {
            print(" + \(primes[i])", terminator: "")
        }
        print()
    }
}

let sieve = PrimeSieve(size: 100000)
printPrimePartition(sieve: sieve, number: 99809, count: 1)
printPrimePartition(sieve: sieve, number: 18, count: 2)
printPrimePartition(sieve: sieve, number: 19, count: 3)
printPrimePartition(sieve: sieve, number: 20, count: 4)
printPrimePartition(sieve: sieve, number: 2017, count: 24)
printPrimePartition(sieve: sieve, number: 22699, count: 1)
printPrimePartition(sieve: sieve, number: 22699, count: 2)
printPrimePartition(sieve: sieve, number: 22699, count: 3)
printPrimePartition(sieve: sieve, number: 22699, count: 4)
printPrimePartition(sieve: sieve, number: 40355, count: 3)

Output:

99809 = 99809
18 = 5 + 13
19 = 3 + 5 + 11
20 cannot be partitioned into 4 primes.
2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
22699 = 22699
22699 = 2 + 22697
22699 = 3 + 5 + 22691
22699 = 2 + 3 + 43 + 22651
40355 = 3 + 139 + 40213

VBScript

Translation of: Rexx

' Partition an integer X into N primes
    dim p(),a(32),b(32),v,g: redim p(64)
    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)): x=t2(0): n=t2(1)
        t3=split(x,"-"): x=clng(t3(0))
        if ubound(t3)=1 then y=clng(t3(1)) else y=x
        t3=split(n,"-"): 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

sub genp(high)
    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)
    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()
    w=b(1)
    if v=g then for i=2 to q: w=w&"+"&b(i): next else w="(not possible)"
    list="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: bu=false
        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
                bu=true: exit for
            end if
        next 's
        if not bu then
            if v=g then exit do
            if v<g then call getp(q)
        end if    
    loop
    wscript.echo "partition "&g&" into "&q&" "&list
end sub 'part

Output:

partition 99809 into 1 primes: 99809
partition 18 into 2 primes: 5+13
partition 19 into 3 primes: 3+5+11
partition 20 into 4 primes: (not possible)
partition 2017 into 24 primes: 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 primes: 22699
partition 22699 into 2 primes: 2+22697
partition 22699 into 3 primes: 3+5+22691
partition 22699 into 4 primes: 2+3+43+22651
partition 40355 into 3 primes: 3+139+40213

Visual Basic .NET

Translation of: Rexx

Works with: Visual Basic .NET version 2011

' 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

Output:

partition 99809 into 1 primes: 99809
partition 18 into 2 primes: 5+13
partition 19 into 3 primes: 3+5+11
partition 20 into 4 primes: (not possible)
partition 2017 into 24 primes: 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 primes: 22699
partition 22699 into 2 primes: 2+22697
partition 22699 into 3 primes: 3+5+22691
partition 22699 into 4 primes: 2+3+43+22651
partition 40355 into 3 primes: 3+139+40213

Wren

Translation of: Kotlin

Library: Wren-math

Library: Wren-fmt

The relevant primes are generated here by a sieve.

import "./math" for Int, Nums
import "./fmt" for Fmt

var primes = Int.primeSieve(1e5)
var foundCombo = false

var findCombo // recursive
findCombo = Fn.new { |k, x, m, n, combo|
    if (k >= m) {
        if (Nums.sum(combo.map { |i| primes[i] }.toList) == x) {
            var s = (m > 1) ? "s" : ""
            Fmt.write("Partitioned $5d with $2d prime$s: ", x, m, s)
            for (i in 0...m) {
                System.write(primes[combo[i]])
                System.write((i < m - 1) ? "+" : "\n")
            }
            foundCombo = true
        }
    } else {
        for (j in 0...n) {
            if (k == 0 || j > combo[k - 1]) {
                combo[k] = j
                if (!foundCombo) findCombo.call(k + 1, x, m, n, combo)
            }
        }
    }
}

var partition = Fn.new { |x, m|
    if (x < 2 || m < 1 || m >= x) Fiber.abort("Invalid argument(s)")
    var n = primes.where { |p| p <= x }.count
    if (n < m) Fiber.abort("Not enough primes")
    var combo = List.filled(m, 0)
    foundCombo = false
    findCombo.call(0, x, m, n, combo)
    if (!foundCombo) {
        var s = (m > 1) ? "s" : ""
        Fmt.print("Partitioned $5d with $2d prime$s: (not possible)", x, m, s)
    }
}

var a = [
    [99809, 1],
    [18, 2],
    [19, 3],
    [20, 4],
    [2017, 24],
    [22699, 1],
    [22699, 2],
    [22699, 3],
    [22699, 4],
    [40355, 3]
]
for (p in a) partition.call(p[0], p[1])

Output:

Partitioned 99809 with  1 prime : 99809
Partitioned    18 with  2 primes: 5+13
Partitioned    19 with  3 primes: 3+5+11
Partitioned    20 with  4 primes: (not possible)
Partitioned  2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with  1 prime : 22699
Partitioned 22699 with  2 primes: 2+22697
Partitioned 22699 with  3 primes: 3+5+22691
Partitioned 22699 with  4 primes: 2+3+43+22651
Partitioned 40355 with  3 primes: 3+139+40213

zkl

Using the prime generator from task Extensible prime generator#zkl.

   // Partition integer N into M unique primes
fcn partition(N,M,idx=0,ps=List()){
   var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve);
   var [const] primes=List();
   while(sieve.peek()<=N){ primes.append(sieve.next()) }
   if(M<2){
      z:=primes.find(N);
      return(if(Void!=z and z>=idx) ps.append(N) else Void);
   }
   foreach z in ([idx..primes.len()-1]){
      p:=primes[z];
      if(p<=N and self.fcn(N-p,M-1,z+1,ps)) return(ps.insert(0,p));
      if(p>N) break;
   }
   Void		// no solution
}

foreach n,m in (T( T(18,2),T(19,3),T(99809,1),T(20,4),T(2017,24),
      T(22699,1),T(22699,2),T(22699,3),T(22699,4),T(40355,3), )){
   ps:=partition(n,m);
   if(ps) println("Partition %d with %d prime(s): %s".fmt(n,m,ps.concat("+")));
   else   println("Can not partition %d with %d prime(s)".fmt(n,m));
}

Output:

Partition 18 with 2 prime(s): 5+13
Partition 19 with 3 prime(s): 3+5+11
Partition 99809 with 1 prime(s): 99809
Can not partition 20 with 4 prime(s)
Partition 2017 with 24 prime(s): 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 with 1 prime(s): 22699
Partition 22699 with 2 prime(s): 2+22697
Partition 22699 with 3 prime(s): 3+5+22691
Partition 22699 with 4 prime(s): 2+3+43+22651
Partition 40355 with 3 prime(s): 3+139+40213