I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

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

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.

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

## 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 goodvoid 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```

## 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., 2017let 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.combinatoricsmath.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
```

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

`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 -> StringjustifyLeft 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 updef 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 \$xdef 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) == \$sumdef 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 emptydef 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/2def 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 \$arydef 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; `

`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 sayvar 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 FALSEend ------------------------------------------ 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: " & resend ------------------------------------------ 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 strend`
`-- 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[[email protected]]];(*Another helper that makes creating the next candidate less verbose*) NextCandidate[{list_, target_}] := With[  {len = [email protected], nextHead = NestWhile[Drop[#, -1] &, list, Total[#] > target &]},  Which[   {} == nextHead, {{}, target},   Total[nextHead] == target && [email protected] == 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 == [email protected], "no solutions found", StringRiffle[list, "+"]],  If[1 == [email protected], "", "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 @@ #, [email protected]#]]] & /@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 = truefor 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

`function partition(integer v, n, idx=0)    if n=1 then        return iff(is_prime(v)?{v}:0)    end if    object res    while 1 do        idx += 1        integer np = get_prime(idx)        if np>=floor(v/2) then exit end if        res = partition(v-np, n-1, idx)        if sequence(res) then return np&res end if    end while    return 0end 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":substitute(trim(sprint(res),"{}"),","," + "))    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' partitionmulti 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```

## 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 [email protected].#+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 = 0num = 0list = 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          okend 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.rsmod 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.rsuse 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.rspub 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)  } }`

## 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 'jsub 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 'iend sub 'genpsub 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 'getpfunction list()    w=b(1)    if v=g then for i=2 to q: w=w&"+"&b(i): next else w="(not possible)"    list="primes: "&wend function 'listsub 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&" "&listend 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/2017Option 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, Numsimport "/fmt" for Fmt var primes = Int.primeSieve(1e5)var foundCombo = false var findCombo // recursivefindCombo = 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 primesfcn 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
```