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

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

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

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

`{-# LANGUAGE TupleSections #-} import Data.List (delete, intercalate) -- PRIME PARTITIONS ----------------------------------------------------------partition :: Int -> Int -> [Int]partition x n  | n <= 1 =    [ x    | last ps == x ]  | otherwise = partition_ ps x n  where    ps = takeWhile (<= x) primes    partition_ ps_ x 1 =      [ x      | x `elem` ps_ ]    partition_ ps_ x n =      let found = foldMap partitionsFound ps_      in nullOr found [] (head found)      where        partitionsFound p =          let r = x - p              rs = partition_ (delete p (takeWhile (<= r) ps_)) r (n - 1)          in nullOr rs [] [p : rs] -- TEST ----------------------------------------------------------------------main :: IO ()main =  mapM_ putStrLn \$  (\(x, n) ->      (intercalate         " -> "         [ justifyLeft 9 ' ' (show (x, n))         , let xs = partition x n           in nullOr xs "(no solution)" (intercalate "+" (show <\$> 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) nullOr  :: Foldable t1  => t1 a -> t -> t -> tnullOr expression nullValue orValue =  if null expression    then nullValue    else orValue primes :: [Int]primes =  2 :  pruned    [3 ..]    (listUnion       [ (p *) <\$> [p ..]       | p <- primes ])  where    pruned :: [Int] -> [Int] -> [Int]    pruned (x:xs) (y:ys)      | x < y = x : pruned xs (y : ys)      | x == y = pruned xs ys      | x > y = pruned (x : xs) ys    listUnion :: [[Int]] -> [Int]    listUnion = foldr union []      where        union (x:xs) ys = x : union_ xs ys        union_ (x:xs) (y:ys)          | x < y = x : union_ xs (y : ys)          | x == y = x : union_ xs ys          | x > y = y : union_ (x : xs) ys`
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```

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

 This example does not show the output mentioned in the task description on this page (or a page linked to from here). Please ensure that it meets all task requirements and remove this message. Note that phrases in task descriptions such as "print and display" and "print and show" for example, indicate that (reasonable length) output be a part of a language's solution.

 This example is incorrect. Please fix the code and remove this message.Details: the partitioning of   40,356   into three primes isn't the lowest primes that are possible, the primes should be:   3,   139,   40213.

Just call the function F[X,N]

`F[x_, n_] :=  Print["Partitioned ", x, " with ", n, " primes: ",   StringRiffle[   ToString /@     Reverse[[email protected]      Sort[Select[IntegerPartitions[x, {n}, [email protected]@[email protected]],         [email protected]@# == n &], Last]], "+"]] F[40355, 3]`

Output:
```Partitioned 40355 with 3 primes: 5+7+40343
```

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

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

## Phix

Using is_prime(), primes[] and add_block() from Extensible_prime_generator#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        while length(primes)<idx do            add_block()        end while        integer np = primes[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":sprint(res))    printf(1,"Partitioned %d into %d primes: %s\n",{v,n,res})end for`
Output:
```Partitioned 99809 into 1 primes: {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 primes: {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}
```

## 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(n, ',', cnt , "->", '+'.join(str(s) for s in c))                break        except:            print(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```

## 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 /*get possible range  and # partitions.*/  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;  end  /*q*/     /*partition  G   into    Q    primes.  */     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.[email protected]._;  return 0/*──────────────────────────────────────────────────────────────────────────────────────*/list: _=p.1;   if \$==g  then  do j=2  to q;  _=_ p.j;  end;     else _= '__(not_possible)'      the= 'primes:';   if q==1  then the= 'prime: ';    return the translate(_,"+ ",' _')/*──────────────────────────────────────────────────────────────────────────────────────*/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
```

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

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

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