Partition an integer x into n primes: Difference between revisions

Add Cowgol
m (→‎{{header|REXX}}: split some DO-END statements, added/changed commands and whitespace, simplified a pluralizer.)
(Add Cowgol)
 
(29 intermediate revisions by 14 users not shown)
Line 11:
 
Show in the output section the sum   '''X'''   and the   '''N'''   primes in ascending order separated by plus ('''+''') signs:
<big> &bull; </big> &nbsp; partition '''99809''' with 1 prime.
<big> &bull; </big> &nbsp; partition '''18''' with 2 primes.
<big> &bull; </big> &nbsp; partition '''19''' with 3 primes.
<big> &bull; </big> &nbsp; partition '''20''' with 4 primes.
<big> &bull; </big> &nbsp; partition '''2017''' with 24 primes.
<big> &bull; </big> &nbsp; partition '''22699''' with 1, 2, 3, <u>and</u> 4 primes.
<big> &bull; </big> &nbsp; partition '''40355''' with 3 primes.
 
The output could/should be shown in a format such as:
 
Partitioned 19 with 3 primes: 3+5+11
 
::* &nbsp; Use any spacing that may be appropriate for the display.
::* &nbsp; You need not validate the input(s).
::* &nbsp; Use the lowest primes possible; &nbsp; use &nbsp;'''18 = 5+13''', &nbsp; not &nbsp; '''18 = 7+11'''.
::* &nbsp; You only need to show one solution.
 
Line 41:
:* &nbsp; [[Sequence of primes by trial division]]
<br><br>
 
=={{header|11l}}==
{{trans|D}}
 
<syntaxhighlight lang="11l">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)</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find the lowest n distinct primes that sum to an integer x #
 
INT max number = 100 000; # largest number we will consider #
# sieve the primes to max number #
[ 1 : max number ]BOOL prime; FOR i TO UPB prime DO prime[ i ] := ODD i OD;
prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR s FROM 3 BY 2 TO ENTIER sqrt( max number ) DO
IF prime[ s ] THEN
FOR p FROM s * s BY s TO UPB prime DO prime[ p ] := FALSE OD
FI
OD;
 
[ 1 : 0 ]INT no partition; # empty array - used if can't partition #
 
# returns n partitioned into p primes or an empty array if n can't be #
# partitioned into p primes, the first prime to try is in start #
PROC partition from = ( INT n, p, start )[]INT:
IF p < 1 OR n < 2 OR start < 2 THEN # invalid parameters #
no partition
ELIF p = 1 THEN # partition into 1 prime - n must be prime #
IF NOT prime[ n ] THEN no partition ELSE n FI
ELIF p = 2 THEN # partition into a pair of primes #
INT half n = n OVER 2;
INT p1 := 0, p2 := 0;
BOOL found := FALSE;
FOR p pos FROM start TO UPB prime WHILE NOT found AND p pos < half n DO
IF prime[ p pos ] THEN
p1 := p pos;
p2 := n - p pos;
found := prime[ p2 ]
FI
OD;
IF NOT found THEN no partition ELSE ( p1, p2 ) FI
ELSE # partition into 3 or more primes #
[ 1 : p ]INT p2;
INT half n = n OVER 2;
INT p1 := 0;
BOOL found := FALSE;
FOR p pos FROM start TO UPB prime WHILE NOT found AND p pos < half n DO
IF prime[ p pos ] THEN
p1 := p pos;
[]INT sub partition = partition from( n - p1, p - 1, p pos + 1 );
IF found := UPB sub partition = p - 1 THEN
# have p - 1 primes summing to n - p1 #
p2[ 1 ] := p1;
p2[ 2 : p ] := sub partition
FI
FI
OD;
IF NOT found THEN no partition ELSE p2 FI
FI # partition from # ;
 
# returns the partition of n into p primes or an empty array if that is #
# not possible #
PROC partition = ( INT n, p )[]INT: partition from( n, p, 2 );
 
# show the first partition of n into p primes, if that is possible #
PROC show partition = ( INT n, p )VOID:
BEGIN
[]INT primes = partition( n, p );
STRING partition info = whole( n, -6 ) + " with " + whole( p, -2 )
+ " prime" + IF p = 1 THEN " " ELSE "s" FI + ": ";
IF UPB primes < LWB primes THEN
print( ( "Partitioning ", partition info, "is not possible" ) )
ELSE
print( ( "Partitioned ", partition info ) );
print( ( whole( primes[ LWB primes ], 0 ) ) );
FOR p pos FROM LWB primes + 1 TO UPB primes DO
print( ( "+", whole( primes[ p pos ], 0 ) ) )
OD
FI;
print( ( newline ) )
END # show partition # ;
 
# test cases #
show partition( 99809, 1 );
show partition( 18, 2 );
show partition( 19, 3 );
show partition( 20, 4 );
show partition( 2017, 24 );
show partition( 22699, 1 );
show partition( 22699, 2 );
show partition( 22699, 3 );
show partition( 22699, 4 );
show partition( 40355, 3 )
 
END
</syntaxhighlight>
{{out}}
<pre>
Partitioned 99809 with 1 prime : 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioning 20 with 4 primes: is not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 prime : 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213
</pre>
 
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">primepart←{
sieve←{
(⊃{0@(1↓⍺×⍳⌊(⍴⍵)÷⍺)⊢⍵}/(1↓⍳⍵),⊂(0,1↓⍵/1))/⍳⍵
}
part←{
0=⍴⍺⍺:⍬
⍵=1:(⍺⍺=⍺)/⍺⍺
0≠⍴r←(⍺-⊃⍺⍺)((1↓⍺⍺)∇∇)⍵-1:(⊃⍺⍺),r
⍺((1↓⍺⍺)∇∇)⍵
}
⍺((sieve ⍺)part)⍵
}
primepart_test←{
tests←(99809 1)(18 2)(19 3)(20 4)(2017 24)
tests,←(22699 1)(22699 2)(22699 3)(22699 4)(40355 3)
{
x n←⍵
p←x primepart n
⍞←'Partition ',(⍕x),' with ',(⍕n),' primes: '
0=⍴p:⍞←'not possible.',⎕TC[2]
⍞←(1↓∊'+',¨⍕¨p),⎕TC[2]
}¨tests
}</syntaxhighlight>
{{out}}
<pre> primepart_test⍬
Partition 99809 with 1 primes: 99809
Partition 18 with 2 primes: 5+13
Partition 19 with 3 primes: 3+5+11
Partition 20 with 4 primes: not possible.
Partition 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partition 22699 with 1 primes: 22699
Partition 22699 with 2 primes: 2+22697
Partition 22699 with 3 primes: 3+5+22691
Partition 22699 with 4 primes: 2+3+43+22651
Partition 40355 with 3 primes: 3+139+40213</pre>
 
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
 
let sieve(n, prime) be
$( let i = 2
0!prime := false
1!prime := false
for i = 2 to n do i!prime := true
while i*i <= n
$( let j = i*i
while j <= n
$( j!prime := false
j := j+i
$)
i := i+1
$)
$)
 
let partition(x, n, prime, p, part) =
p > x -> false,
n = 1 -> valof $( !part := x; resultis x!prime $),
valof
$( p := p+1 repeatuntil p!prime
!part := p
if partition(x-p, n-1, prime, p, part+1) resultis true
resultis partition(x, n, prime, p, part)
$)
 
let showpart(n, part) be
$( writef("%N", !part)
unless n=1 do
$( wrch('+')
showpart(n-1, part+1)
$)
$)
 
let show(x, n, prime) be
$( let part = vec 32
writef("Partitioned %N with %N prime%S: ", x, n, n=1->"", "s")
test partition(x, n, prime, 1, part)
do showpart(n, part)
or writes("not possible")
newline()
$)
 
let start() be
$( let prime = getvec(100000)
 
let tests = table 99809,1, 18,2, 19,3, 20,4, 2017,24,
22699,1, 22699,2, 22699,3, 22699,4, 40355,3
 
sieve(100000, prime)
for t = 0 to 9 do show(tests!(t*2), tests!(t*2+1), prime)
freevec(prime)
$)</syntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|C}}==
{{works with|C99}}
<langsyntaxhighlight lang="c">#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
Line 172 ⟶ 442:
sieve_destroy(&s);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 190 ⟶ 460:
=={{header|C sharp}}==
{{works with|C sharp|7}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections;
using System.Collections.Generic;
Line 267 ⟶ 537:
}
 
}</langsyntaxhighlight>
{{out}}
<pre>
Line 284 ⟶ 554:
=={{header|C++}}==
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <functional>
#include <iostream>
Line 422 ⟶ 692:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 prime 99809
Line 434 ⟶ 704:
Partitioned 22699 with 4 primes 2+3+43+22651
Partitioned 40355 with 3 primes 3+139+40213</pre>
 
=={{header|CLU}}==
<syntaxhighlight lang="clu">isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0 = 0 then return(s) end
x1: int := (x0 + s/x0) / 2
while x1 < x0 do
x0, x1 := x1, (x0 + s/x0) / 2
end
return(x0)
end isqrt
 
primes = proc (n: int) returns (sequence[int])
prime: array[bool] := array[bool]$fill(1, n, true)
prime[1] := false
for p: int in int$from_to(2, isqrt(n)) do
for c: int in int$from_to_by(p*p, n, p) do
prime[c] := false
end
end
 
pr: array[int] := array[int]$predict(1, n)
for p: int in array[bool]$indexes(prime) do
if prime[p] then array[int]$addh(pr, p) end
end
 
return(sequence[int]$a2s(pr))
end primes
 
partition_sum = proc (x, n: int, nums: sequence[int])
returns (sequence[int])
signals (impossible)
if n<=0 cor sequence[int]$empty(nums) then signal impossible end
 
if n=1 then
for k: int in sequence[int]$elements(nums) do
if x=k then return(sequence[int]$[x]) end
end
signal impossible
end
 
k: int := sequence[int]$bottom(nums)
rest: sequence[int] := sequence[int]$reml(nums)
 
return(sequence[int]$addl(partition_sum(x-k, n-1, rest), k))
except when impossible:
return(partition_sum(x, n, rest))
resignal impossible
end
end partition_sum
 
prime_partition = proc (x, n: int)
returns (sequence[int])
signals (impossible)
return(partition_sum(x, n, primes(x))) resignal impossible
end prime_partition
 
format_sum = proc (nums: sequence[int]) returns (string)
result: string := ""
for n: int in sequence[int]$elements(nums) do
result := result || "+" || int$unparse(n)
end
return(string$rest(result, 2))
end format_sum
 
start_up = proc ()
test = struct[x: int, n: int]
tests: sequence[test] := sequence[test]$[
test${x:99809,n:1}, test${x:18,n:2}, test${x:19,n:3}, test${x:20,n:4},
test${x:2017,n:24}, test${x:22699,n:1}, test${x:22699,n:2},
test${x:22699,n:3}, test${x:22699,n:4}, test${x:40355,n:3}
]
 
po: stream := stream$primary_output()
for t: test in sequence[test]$elements(tests) do
stream$puts(po, "Partitioned " || int$unparse(t.x) || " with "
|| int$unparse(t.n) || " primes: ")
stream$putl(po, format_sum(prime_partition(t.x, t.n)))
except when impossible:
stream$putl(po, "not possible.")
end
end
end start_up</syntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible.
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
 
const MAXPRIM := 100000;
const MAXPRIM_B := (MAXPRIM >> 3) + 1;
 
var primebits: uint8[MAXPRIM_B];
typedef ENTRY_T is @indexof primebits;
 
sub pentry(n: uint32): (ent: ENTRY_T, bit: uint8) is
ent := (n >> 3) as ENTRY_T;
bit := (n & 7) as uint8;
end sub;
 
sub setprime(n: uint32, prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
var one: uint8 := 1;
primebits[ent] := primebits[ent] & ~(one << bit);
primebits[ent] := primebits[ent] | (prime << bit);
end sub;
 
sub prime(n: uint32): (prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
prime := (primebits[ent] >> bit) & 1;
end sub;
 
sub sieve() is
MemSet(&primebits[0], 0xFF, @bytesof primebits);
setprime(0, 0);
setprime(1, 0);
var p: uint32 := 2;
while p*p <= MAXPRIM loop
var c := p*p;
while c <= MAXPRIM loop
setprime(c, 0);
c := c + p;
end loop;
p := p + 1;
end loop;
end sub;
 
sub nextprime(p: uint32): (r: uint32) is
r := p;
loop
r := r + 1;
if prime(r) != 0 then break; end if;
end loop;
end sub;
 
sub partition(x: uint32, n: uint8, part: [uint32]): (r: uint8) is
record State is
x: uint32;
n: uint8;
p: uint32;
part: [uint32];
end record;
 
var stack: State[128];
var sp: @indexof stack := 0;
 
sub Push(x: uint32, n: uint8, p: uint32, part: [uint32]) is
stack[sp].x := x;
stack[sp].n := n;
stack[sp].p := p;
stack[sp].part := part;
sp := sp + 1;
end sub;
 
sub Pull(): (x: uint32, n: uint8, p: uint32, part: [uint32]) is
sp := sp - 1;
x := stack[sp].x;
n := stack[sp].n;
p := stack[sp].p;
part := stack[sp].part;
end sub;
 
r := 0;
Push(x, n, 1, part);
while sp > 0 loop
var p: uint32;
(x, n, p, part) := Pull();
p := nextprime(p);
 
if x < p then
continue;
end if;
 
if n == 1 then
if prime(x) != 0 then
r := 1;
[part] := x;
return;
end if;
else
[part] := p;
Push(x, n, p, part);
Push(x-p, n-1, p, @next part);
end if;
end loop;
r := 0;
end sub;
 
sub showpartition(x: uint32, n: uint8) is
print("Partitioning ");
print_i32(x);
print(" with ");
print_i8(n);
print(" primes: ");
 
var part: uint32[64];
if partition(x, n, &part[0]) != 0 then
print_i32(part[0]);
var i: @indexof part := 1;
while i < n as @indexof part loop
print_char('+');
print_i32(part[i]);
i := i + 1;
end loop;
else
print("Not possible");
end if;
print_nl();
end sub;
 
sieve();
 
record Test is
x: uint32;
n: uint8;
end record;
 
var tests: Test[] := {
{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
{22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}
};
 
var test: @indexof tests := 0;
while test < @sizeof tests loop
showpartition(tests[test].x, tests[test].n);
test := test + 1;
end loop;</syntaxhighlight>
{{out}}
<pre>Partitioning 99809 with 1 primes: 99809
Partitioning 18 with 2 primes: 5+13
Partitioning 19 with 3 primes: 3+5+11
Partitioning 20 with 4 primes: Not possible
Partitioning 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioning 22699 with 1 primes: 22699
Partitioning 22699 with 2 primes: 2+22697
Partitioning 22699 with 3 primes: 3+5+22691
Partitioning 22699 with 4 primes: 2+3+43+22651
Partitioning 40355 with 3 primes: 3+139+40213</pre>
 
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight Dlang="d">import std.array : array;
import std.range : take;
import std.stdio;
Line 553 ⟶ 1,073:
partition(p[0], p[1]);
}
}</langsyntaxhighlight>
 
{{out}}
Line 569 ⟶ 1,089:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017
let rcTask n ng =
Line 579 ⟶ 1,099:
|Some n->printfn "%d is the sum of %A" ng n
|_ ->printfn "No Solution"
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 595 ⟶ 1,115:
 
=={{header|Factor}}==
<langsyntaxhighlight lang="factor">USING: formatting fry grouping kernel math.combinatorics
math.parser math.primes sequences ;
 
Line 608 ⟶ 1,128:
{ 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</langsyntaxhighlight>
{{out}}
<pre>
Line 621 ⟶ 1,141:
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213
</pre>
 
=={{header|Fortran}}==
{{trans|VBScript}}
<syntaxhighlight lang="FORTRAN">
module primes_module
implicit none
integer,allocatable :: p(:)
integer :: a(0:32), b(0:32)
integer,private :: sum_primes, number
contains
!
subroutine setnum(val)
implicit none
integer :: val
number = val
return
end subroutine setnum
!
subroutine init(thesize)
implicit none
integer :: thesize
!
allocate(p(thesize))
p=0
a=0
b=0
return
end subroutine init
!
subroutine genp(high) ! Store all primes up to high in the array p
integer, intent(in) :: high
integer :: i, numprimes, j,k
logical*1 :: bk(0:high)
!
bk = .false.
p = 0
a = 0
b = 0
call eratosthenes(bk , high)
j = 0
numprimes = count(bk)
k = 0
do i = 1,high
if(bk(i))then
j = j+1
p(j) = i
if(j==numprimes)exit !No need to loop more, all primes stored
endif
end do
print*,'numprimes',numprimes, i,p(j)
return
end subroutine genp
 
subroutine getp(z) ! used to update the zth prime number in the sequence of primes that are being used to partition the integer number.
integer :: z
integer :: w
!
if (a(z) == 0)a(z) = a(z-1)
a(z) = a(z) + 1
b(z) = p(a(z))
return
end subroutine getp
 
subroutine part(num_found)
integer, intent(in) :: num_found
integer :: i, s, k, r
logical :: bu
a = 0
do i = 1, num_found
call getp(i)
end do
infinite: do
sum_primes = 0
bu = .false.
nextin:do s = 1, num_found
sum_primes = sum_primes + b(s) !Adds the sth prime to sum_primes.
if (sum_primes > number) then !If the sum of primes exceeds number:
if (s == 1)then
exit infinite !If only one prime has been added, exit the infinite loop.
endif
a(s:num_found) = 0 ! Resets the indices of the primes from s to num_found
do r = s - 1, num_found ! Gets the next set of primes from s-1 to num_found
call getp(r)
end do
bu = .true. ! Sets bu to true and exits the loop over the primes
exit nextin
end if
end do nextin
if (.not. bu) then ! If bu is false (meaning the sum of primes does not exceed number)
if (sum_primes == number) exit infinite !We got it so go
if (sum_primes < number) then
call getp(num_found) ! If the sum of primes is less than number, gets the next prime
else
error stop " Something wrong here!"
endif
endif
end do infinite
write( *,'(/,a,1x,i0,1x,a,1x,i0,1x,a)',advance='yes') "Partition", number, "into", num_found,trim(adjustl(list(num_found)))
end subroutine part
!
function list(num_found)
integer, intent(in) :: num_found
integer :: i
character(len=128) :: list
character(len = 10):: pooka
!
write(list,'(i0)') b(1)
if (sum_primes == number) then
do i = 2, num_found
pooka = ''
write(pooka,'(i0)') b(i)
list = trim(list) // " + " // adjustl(pooka)
end do
else
list = "(not possible)"
end if
list = "primes: " // list
end function list
!
subroutine eratosthenes(p , n)
implicit none
!
! dummy arguments
!
integer :: n
logical*1 , dimension(0:*) :: p
intent (in) n
intent (inout) p
!
! local variables
!
integer :: i
integer :: ii
logical :: oddeven
integer :: pr
!
p(0:n) = .false.
p(1) = .false.
p(2) = .true.
oddeven = .true.
do i = 3 , n,2
p(i) = .true.
end do
do i = 2 , int(sqrt(float(n)))
ii = i + i
if( p(i) )then
do pr = i*i , n , ii
p(pr) = .false.
end do
end if
end do
return
end subroutine eratosthenes
 
end module primes_module
 
program prime_partition
use primes_module
implicit none
integer :: x, n,i
integer :: xx,yy
integer :: values(10,2)
! The given dataset from Rosetta Code
! partition 99809 with 1 prime.
! partition 18 with 2 primes.
! partition 19 with 3 primes.
! partition 20 with 4 primes.
! partition 2017 with 24 primes.
! partition 22699 with 1, 2, 3, and 4 primes.
! partition 40355 with 3 primes.
values(1,:) = (/99809,1/)
values(2,:) = (/18,2/)
values(3,:) = (/19,3/)
values(4,:) = (/20,4/)
values(5,:) = (/2017,24/)
values(6,:) = (/22699, 1/)
values(7,:) = (/22699, 2/)
values(8,:) = (/22699, 3/)
values(9,:) = (/22699, 4/)
values(10,:) = (/40355, 3/)
i = maxval(values(1:10,1))*2
call init(i) ! Set up a few basics
call genp(i) ! Generate primes up to i
do i = 1,10
call setnum( values(i,1))
call part(values(i,2))
end do
Stop 'Successfully completed'
end program prime_partition
</syntaxhighlight>
{{out}}
<pre>
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
 
</pre>
 
Line 626 ⟶ 1,350:
{{trans|Kotlin}}
... though uses a sieve to generate the relevant primes.
<langsyntaxhighlight lang="go">package main
 
import (
Line 737 ⟶ 1,461:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 754 ⟶ 1,478:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.BoolList (booldelete, intercalate)
import Data.Numbers.Primes (primes)
import Data.ListBool (delete, intercalatebool)
 
-------------------- PRIME PARTITIONS ---------------------
Line 785 ⟶ 1,509:
[ justifyLeft 9 ' ' (show (x, n))
, let xs = partitions x n
in bool (intercalate "+" (show <$> xs)) "(no solution)" (null xs)
(tail $ concatMap (('+' :) . show) xs)
"(no solution)"
(null xs)
]) <$>
concat
Line 795 ⟶ 1,522:
------------------------- GENERIC -------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)</langsyntaxhighlight>
{{Out}}
<pre>(99809,1) -> 99809
Line 809 ⟶ 1,536:
 
=={{header|J}}==
<syntaxhighlight lang="j">
<lang j>
load 'format/printf'
Line 851 ⟶ 1,578:
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
</syntaxhighlight>
</lang>
 
 
Line 870 ⟶ 1,597:
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.util.Arrays;
import java.util.stream.IntStream;
 
Line 946 ⟶ 1,673:
partition(40355, 3);
}
}</langsyntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 prime: 99809
Line 959 ⟶ 1,686:
Partitioned 40355 with 3 primes: 3+139+40213</pre>
 
=={{header|jq}}==
'''Works with jq and with gojq, the Go implementation of jq'''
 
'''Prime-number functions'''
<syntaxhighlight lang="jq">
# Is the input integer a prime?
def is_prime:
if . == 2 then true
else 2 < . and . % 2 == 1 and
. as $in
| (($in + 1) | sqrt) as $m
| (((($m - 1) / 2) | floor) + 1) as $max
| all( range(1; $max) ; $in % ((2 * .) + 1) > 0 )
end;
 
# Is the input integer a prime?
# `previous` should be a sorted array of consecutive primes
# greater than 1 and at least including the greatest prime less than (.|sqrt)
def is_prime(previous):
. as $in
| (($in + 1) | sqrt) as $sqrt
| first(previous[]
| if . > $sqrt then 1
elif 0 == ($in % .) then 0
else empty
end) // 1
| . == 1;
 
# This assumes . is an array of consecutive primes beginning with [2,3]
def next_prime:
. as $previous
| (2 + .[-1] )
| until(is_prime($previous); . + 2) ;
 
# Emit primes from 2 up
def primes:
# The helper function has arity 0 for TCO
# It expects its input to be an array of previously found primes, in order:
def next:
. as $previous
| ($previous|next_prime) as $next
| $next, (($previous + [$next]) | next) ;
2, 3, ([2,3] | next);
 
# The primes less than or equal to $x
def primes($x):
label $out
| primes | if . > $x then break $out else . end;
 
</syntaxhighlight>
'''Helper function'''
<syntaxhighlight lang="jq"># Emit a stream consisting of arrays, a, of $n items from the input array,
# preserving order, subject to (a|add) == $sum
def take($n; $sum):
def take:
. as [$m, $in, $s]
| if $m==0 and $s == 0 then []
elif $m==0 or $s <= 0 then empty
else range(0;$in|length) as $i
| $in[$i] as $x
| if $x > $s then empty
else [$x] + ([$m-1, $in[$i+1:], $s - $x] | take)
end
end;
[$n, ., $sum] | take;</syntaxhighlight>
 
'''Partitioning an integer into $n primes'''
<syntaxhighlight lang="jq"># This function emits a possibly empty stream of arrays.
# Assuming $primes is primes(.), each array corresponds to a
# partition of the input into $n distinct primes.
# The algorithm is unoptimized.
# The output is a stream of arrays, which would be empty
def primepartition($n; $primes):
. as $x
| if $n == 1
then if $primes[-1] == $x then [$x] else null end
else (if $primes[-1] == $x then $primes[:-1] else $primes end) as $primes
| ($primes | take($n; $x))
end ;
 
# See primepartition/2
def primepartition($n):
. as $x
| if $n == 1
then if is_prime then [.] else null end
else primepartition($n; [primes($x)])
end;
 
# Compute first(primepartition($n)) for each $n in the array $ary
def primepartitions($ary):
. as $x
| [primes($x)] as $px
| $ary[] as $n
| $x
| first(primepartition($n; $px));
 
def task($x; $n):
def pp:
if . then join("+") else "(not possible)" end;
 
if $n|type == "array" then task($x; $n[])
else "A partition of \($x) into \($n) parts: \(first($x | primepartition($n)) | pp )"
end;
</syntaxhighlight>
 
'''The tasks'''
<syntaxhighlight lang="jq">task(18; 2),
task(19; 3),
task(20; 4),
task(2017; 24),
task(22699; [1,2,3,4]),
task(40355; 3)</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="julia">using Primes, Combinatorics
 
function primepartition(x::Int64, n::Int64)
Line 981 ⟶ 1,831:
println("Partition of ", x, " into ", n, " primes: ",
isempty(ans) ? "impossible" : join(ans, " + "))
end</langsyntaxhighlight>
 
{{output}}
Line 999 ⟶ 1,849:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="scala">// version 1.1.2
 
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning
Line 1,082 ⟶ 1,932:
)
for (p in a) partition(p.first, p.second)
}</langsyntaxhighlight>
 
{{out}}
Line 1,101 ⟶ 1,951:
Using the prime generator class "sieve" from task [[Extensible prime generator#Lingo]].
 
<langsyntaxhighlight Lingolang="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>
Line 1,155 ⟶ 2,005:
delete char (str.length+1-delim.length) to str.length of str
return str
end</langsyntaxhighlight>
 
<langsyntaxhighlight Lingolang="lingo">-- main
_global.sieve = script("sieve").new()
 
Line 1,169 ⟶ 2,019:
showPrimePartition(22699, 3)
showPrimePartition(22699, 4)
showPrimePartition(40355, 3)</langsyntaxhighlight>
 
{{out}}
Line 1,185 ⟶ 2,035:
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">NextPrimeMemo[n_] := (NextPrimeMemo[n] = NextPrime[n]);(*This improves performance by 30% or so*)
PrimeList[count_] := Prime/@Range[count];(*Just a helper to create an initial list of primes of the desired length*)
AppendPrime[list_] := Append[list,NextPrimeMemo[Last@list]];(*Another helper that makes creating the next candidate less verbose*)
 
NextCandidate[{list_, target_}] :=
{{incomplete|Mathematica| <br><br> the output for partitioning of <br> '''42017''', &nbsp; '''22699''', and ''' 40355''' <br> isn't shown. <br><br>}}
With[
{len = Length@list, nextHead = NestWhile[Drop[#, -1] &, list, Total[#] > target &]},
Which[
{} == nextHead, {{}, target},
Total[nextHead] == target && Length@nextHead == len, {nextHead, target},
True, {NestWhile[AppendPrime, MapAt[NextPrimeMemo, nextHead, -1], Length[#] < Length[list] &], target}
]
];(*This is the meat of the matter. If it determines that the job is impossible, it returns a structure with an empty list of summands. If the input satisfies the success criteria, it just returns it (this will be our fixed point). Otherwise, it generates a subsequent candidate.*)
 
FormatResult[{list_, number_}, targetCount_] :=
This can be done with IntegerPartitions:
StringForm[
<lang Mathematica>partition[x_,n_]:= "Partitioned "<>ToString[x]<>" with "<>ToString[n]<>" primes: "<>StringRiffle[
"Partitioned `1` with `2` prime`4`: `3`",
ToString/@First[Sort[Sort/@Select[IntegerPartitions[x,{n},Prime/@Range[PrimePi[x]]],Length[Union[#]]===n&]],{"impossible"}]
number,
,"+"]
targetCount,
If[0 == Length@list, "no solutions found", StringRiffle[list, "+"]],
If[1 == Length@list, "", "s"]]; (*Just a helper for pretty-printing the output*)
 
PrimePartition[number_, count_] := FixedPoint[NextCandidate, {PrimeList[count], number}];(*This is where things kick off. NextCandidate will eventually return the failure format or a success, and either of those are fixed points of the function.*)
partition[18, 2]
 
partition[19, 3]
TestCases =
partition[20, 4]</lang>
{
{99809, 1},
{18, 2},
{19, 3},
{20, 4},
{2017, 24},
{22699, 1},
{22699, 2},
{22699, 3},
{22699, 4},
{40355, 3}
};
 
TimedResults = ReleaseHold[Hold[AbsoluteTiming[FormatResult[PrimePartition @@ #, Last@#]]] & /@TestCases](*I thought it would be interesting to include the timings, which are in seconds*)
 
TimedResults // TableForm</syntaxhighlight>
 
 
{{out}}
<pre>0.111699 Partitioned 99809 with 1 prime: 99809
<pre>
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: impossibleno 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
</pre>
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</pre>
 
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math, sugar
 
const N = 100_000
 
# Fill a sieve of Erathostenes.
var isPrime {.noInit.}: array[2..N, bool]
for item in isPrime.mitems: item = true
for n in 2..int(sqrt(N.toFloat)):
if isPrime[n]:
for k in countup(n * n, N, n):
isPrime[k] = false
 
# Build list of primes.
let primes = collect(newSeq):
for n in 2..N:
if isPrime[n]: n
 
 
proc partition(n, k: int; start = 0): seq[int] =
## Partition "n" in "k" primes starting at position "start" in "primes".
## Return the list of primes or an empty list if partitionning is impossible.
 
if k == 1:
return if isPrime[n] and n >= primes[start]: @[n] else: @[]
 
for i in start..primes.high:
let a = primes[i]
if n - a <= 1: break
result = partition(n - a, k - 1, i + 1)
if result.len != 0:
return a & result
 
 
when isMainModule:
 
import strutils
 
func plural(k: int): string =
if k <= 1: "" else: "s"
 
for (n, k) in [(99809, 1), (18, 2), (19, 3), (20, 4),
(2017, 24), (22699, 1), (22699, 2),
(22699, 3), (22699, 4), (40355, 3)]:
let part = partition(n, k)
if part.len == 0:
echo n, " cannot be partitionned into ", k, " prime", plural(k)
else:
echo n, " = ", part.join(" + ")</syntaxhighlight>
 
{{out}}
<pre>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</pre>
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">partDistinctPrimes(x,n,mn=2)=
{
if(n==1, return(if(isprime(x) && mn<=x, [x], 0)));
Line 1,242 ⟶ 2,189:
}
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]))</langsyntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 prime: 99809
Line 1,258 ⟶ 2,205:
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.
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory ":all";
 
sub prime_partition {
Line 1,272 ⟶ 2,219:
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";
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,289 ⟶ 2,236:
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>function partition(integer v, n, idx=0)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
if n=1 then
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (join(fmt))</span>
return iff(is_prime(v)?{v}:0)
<span style="color: #008080;">function</span> <span style="color: #000000;">partition</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
object res
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)?{</span><span style="color: #000000;">v</span><span style="color: #0000FF;">}:</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
while 1 do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
idx += 1
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
integer np = get_prime(idx)
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
if np>=floor(v/2) then exit end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">np</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
res = partition(v-np, n-1, idx)
<span style="color: #008080;">if</span> <span style="color: #000000;">np</span><span style="color: #0000FF;">>=</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if sequence(res) then return np&res end if
<span style="color: #004080;">object</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">partition</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">-</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
return 0
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
constant tests = {{99809, 1},
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
{18, 2},
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
{19, 3},
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
{20, 4},
{2017, 24},
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">99809</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
{22699, 1},
<span style="color: #0000FF;">{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
{22699, 2},
<span style="color: #0000FF;">{</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
{22699, 3},
<span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span>
{22699, 4},
<span style="color: #0000FF;">{</span><span style="color: #000000;">2017</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">24</span><span style="color: #0000FF;">},</span>
{40355, 3}}
<span style="color: #0000FF;">{</span><span style="color: #000000;">22699</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
 
<span style="color: #0000FF;">{</span><span style="color: #000000;">22699</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
for i=1 to length(tests) do
<span style="color: #0000FF;">{</span><span style="color: #000000;">22699</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
integer {v,n} = tests[i]
<span style="color: #0000FF;">{</span><span style="color: #000000;">22699</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span>
object res = partition(v,n)
<span style="color: #0000FF;">{</span><span style="color: #000000;">40355</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}}</span>
res = iff(res=0?"not possible":substitute(trim(sprint(res),"{}"),","," + "))
printf(1,"Partition %d into %d primes: %s\n",{v,n,res})
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for</lang>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">partition</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"not possible"</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Partition %d into %d primes: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,337 ⟶ 2,290:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<langsyntaxhighlight lang="prolog">prime_partition(N, 1, [N], Min):-
is_prime(N),
N > Min,
Line 1,380 ⟶ 2,333:
print_prime_partition(22699, 3),
print_prime_partition(22699, 4),
print_prime_partition(40355, 3).</langsyntaxhighlight>
 
Module for finding prime numbers up to some limit:
<langsyntaxhighlight lang="prolog">:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.
 
Line 1,424 ⟶ 2,377:
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</langsyntaxhighlight>
 
{{out}}
Line 1,441 ⟶ 2,394:
 
=={{header|Python}}==
<langsyntaxhighlight Pythonlang="python">from itertools import combinations as cmb
 
 
Line 1,475 ⟶ 2,428:
except StopIteration:
print(repr((n, cnt)) + " -> Not possible")
break</langsyntaxhighlight>
{{out}}
<pre>(99809, 1) -> 99809
Line 1,489 ⟶ 2,442:
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
(require math/number-theory)
 
Line 1,521 ⟶ 2,474:
(report-partition 22699 3)
(report-partition 22699 4)
(report-partition 40355 3))</langsyntaxhighlight>
 
{{out}}
Line 1,540 ⟶ 2,493:
{{works with|Rakudo|2018.10}}
 
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
 
Line 1,557 ⟶ 2,510:
say (sprintf "Partition %5d into %2d prime piece", $number, $parts),
$parts == 1 ?? ': ' !! 's: ', join '+', partition($number, $parts) || 'not possible'
}</langsyntaxhighlight>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Line 1,571 ⟶ 2,524:
Partition 40355 into 3 prime pieces: 3+139+40213</pre>
 
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Each Test <Tests>>;
};
 
Tests {
= (99809 1) (18 2) (19 3) (20 4) (2017 24)
(22699 1) (22699 2) (22699 3) (22699 4) (40355 3);
};
 
Test {
(s.X s.N) =
<Prout 'Partitioned ' <Symb s.X> ' with ' <Symb s.N> ' primes: '
<Format <PrimePartition s.X s.N>>>;
};
 
Format {
F = 'not possible';
T s.N = <Symb s.N>;
T s.N e.X = <Symb s.N> '+' <Format T e.X>;
};
 
PrimePartition {
s.X s.N = <Partition s.X s.N <Primes s.X>>;
};
 
Partition {
s.X 1 e.Nums, e.Nums: {
e.1 s.X e.2 = T s.X;
e.1 = F;
};
s.X s.N = F;
s.X s.N s.Num e.Nums, <Compare s.X s.Num>: '-' =
<Partition s.X s.N e.Nums>;
s.X s.N s.Num e.Nums,
<Partition <- s.X s.Num> <- s.N 1> e.Nums>: {
T e.List = T s.Num e.List;
F = <Partition s.X s.N e.Nums>;
};
};
 
Primes {
s.N = <Sieve <Iota 2 s.N>>;
};
 
Iota {
s.End s.End = s.End;
s.Start s.End = s.Start <Iota <+ 1 s.Start> s.End>;
};
 
Cross {
s.Step e.List = <Cross (s.Step 1) s.Step e.List>;
(s.Step s.Skip) = ;
(s.Step 1) s.Item e.List = X <Cross (s.Step s.Step) e.List>;
(s.Step s.N) s.Item e.List = s.Item <Cross (s.Step <- s.N 1>) e.List>;
};
 
Sieve {
= ;
X e.List = <Sieve e.List>;
s.N e.List = s.N <Sieve <Cross s.N e.List>>;
};
 
Each {
s.F = ;
s.F t.X e.R = <Mu s.F t.X> <Each s.F e.R>;
};</syntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213</pre>
=={{header|REXX}}==
Usage note: &nbsp; entering ranges of &nbsp; '''X''' &nbsp; and &nbsp; '''N''' &nbsp; numbers (arguments) from the command line:
Line 1,577 ⟶ 2,608:
which means: &nbsp; partition all integers (inclusive) from &nbsp; '''X''' ──► '''Y''' &nbsp; with &nbsp; '''N''' ──► '''M''' &nbsp; primes.
<br>The &nbsp; ''to'' &nbsp; number &nbsp; ('''Y''' &nbsp; or &nbsp; '''M''') &nbsp; can be omitted.
<langsyntaxhighlight lang="rexx">/*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.*/
Line 1,587 ⟶ 2,619:
if m=='' | m=="," then m= n /* " " " " " " */
call genP y /*generate Y number of primes. */
do g=x to y do g=x to y /*partition X ───► Y into partitions.*/
do q=n to m; call part 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. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Line 1,600 ⟶ 2,633:
end /*k*/ /* [↓] a prime (J) has been found. */
#= # + 1; @.#= j /*bump prime count; assign prime to @.*/
end /*j*/; return
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
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?*/
Line 1,627 ⟶ 2,659:
end /*!*/ /* [↑] Is sum too low? Bump a prime.*/
say 'partitioned' center(g,9) "into" center(q, 5) list()
return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the input of: &nbsp; <tt> 99809 1 &nbsp; 18 2 &nbsp; 19 3 &nbsp;20 4 &nbsp; 2017 24 &nbsp; 22699 1-4 &nbsp; 40355 </tt>}}
<pre>
Line 1,643 ⟶ 2,675:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Partition an integer X into N primes
 
Line 1,715 ⟶ 2,747:
next
return items
</syntaxhighlight>
</lang>
Output:
<pre>
Line 1,731 ⟶ 2,763:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">require "prime"
 
def prime_partition(x, n)
Line 1,745 ⟶ 2,777:
puts "Partitioned #{prime} with #{num} primes: #{str}"
end
</syntaxhighlight>
</lang>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Line 1,757 ⟶ 2,789:
Partitioned 22699 with 4 primes: 2 + 3 + 43 + 22651
Partitioned 40355 with 3 primes: 3 + 139 + 40213
</pre>
 
=={{header|Rust}}==
{{trans|C}}
<syntaxhighlight lang="rust">// main.rs
mod bit_array;
mod prime_sieve;
 
use prime_sieve::PrimeSieve;
 
fn find_prime_partition(
sieve: &PrimeSieve,
number: usize,
count: usize,
min_prime: usize,
primes: &mut Vec<usize>,
index: usize,
) -> bool {
if count == 1 {
if number >= min_prime && sieve.is_prime(number) {
primes[index] = number;
return true;
}
return false;
}
for p in min_prime..number {
if sieve.is_prime(p)
&& find_prime_partition(sieve, number - p, count - 1, p + 1, primes, index + 1)
{
primes[index] = p;
return true;
}
}
false
}
 
fn print_prime_partition(sieve: &PrimeSieve, number: usize, count: usize) {
let mut primes = vec![0; count];
if !find_prime_partition(sieve, number, count, 2, &mut primes, 0) {
println!("{} cannot be partitioned into {} primes.", number, count);
} else {
print!("{} = {}", number, primes[0]);
for i in 1..count {
print!(" + {}", primes[i]);
}
println!();
}
}
 
fn main() {
let s = PrimeSieve::new(100000);
print_prime_partition(&s, 99809, 1);
print_prime_partition(&s, 18, 2);
print_prime_partition(&s, 19, 3);
print_prime_partition(&s, 20, 4);
print_prime_partition(&s, 2017, 24);
print_prime_partition(&s, 22699, 1);
print_prime_partition(&s, 22699, 2);
print_prime_partition(&s, 22699, 3);
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
}</syntaxhighlight>
 
<syntaxhighlight lang="rust">// prime_sieve.rs
use crate::bit_array;
 
pub struct PrimeSieve {
composite: bit_array::BitArray,
}
 
impl PrimeSieve {
pub fn new(limit: usize) -> PrimeSieve {
let mut sieve = PrimeSieve {
composite: bit_array::BitArray::new(limit / 2),
};
let mut p = 3;
while p * p <= limit {
if !sieve.composite.get(p / 2 - 1) {
let inc = p * 2;
let mut q = p * p;
while q <= limit {
sieve.composite.set(q / 2 - 1, true);
q += inc;
}
}
p += 2;
}
sieve
}
pub fn is_prime(&self, n: usize) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
!self.composite.get(n / 2 - 1)
}
}</syntaxhighlight>
 
<syntaxhighlight lang="rust">// bit_array.rs
pub struct BitArray {
array: Vec<u32>,
}
 
impl BitArray {
pub fn new(size: usize) -> BitArray {
BitArray {
array: vec![0; (size + 31) / 32],
}
}
pub fn get(&self, index: usize) -> bool {
let bit = 1 << (index & 31);
(self.array[index >> 5] & bit) != 0
}
pub fn set(&mut self, index: usize, new_val: bool) {
let bit = 1 << (index & 31);
if new_val {
self.array[index >> 5] |= bit;
} else {
self.array[index >> 5] &= !bit;
}
}
}</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|Scala}}==
<langsyntaxhighlight Scalalang="scala">object PartitionInteger {
 
def sieve(nums: LazyList[Int]): LazyList[Int] =
Line 1,808 ⟶ 2,977:
}
 
}</langsyntaxhighlight>
 
=={{header|SETL}}==
<syntaxhighlight lang="setl">program primes_partition;
tests := [[99809,1], [18,2], [19,3], [20,4], [2017,24],
[22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
 
loop for [x, n] in tests do
nprint("Partitioned",x,"with",n,"primes:");
if (p := partition(x,n)) = om then
print(" not possible");
else
print(" " + (+/["+" + str pr : pr in p])(2..));
end if;
end loop;
 
proc partition(x,n);
return findpart(x,n,sieve(x));
end proc;
 
proc findpart(x,n,nums);
if n=1 then
return if x in nums then [x] else om end;
end if;
 
loop while nums /= [] do
k fromb nums;
if (l := findpart(x-k, n-1, nums)) /= om then
return [k] + l;
end if;
end loop;
return om;
end proc;
 
proc sieve(n);
primes := [1..n];
primes(1) := om;
loop for p in [2..floor sqrt n] do
loop for c in [p*p, p*p+p..n] do
primes(c) := om;
end loop;
end loop;
return [p : p in primes | p /= om];
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213</pre>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">func prime_partition(num, parts) {
 
if (parts == 1) {
Line 1,835 ⟶ 3,059:
say ("Partition %5d into %2d prime piece" % (num, parts),
parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible')
}</langsyntaxhighlight>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Line 1,848 ⟶ 3,072:
Partition 22699 into 4 prime pieces: 2+3+43+22651
Partition 40355 into 3 prime pieces: 3+139+40213</pre>
 
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">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)</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|VBScript}}==
{{trans|Rexx}}
<langsyntaxhighlight lang="vb">' 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"
Line 1,914 ⟶ 3,259:
wscript.echo "partition "&g&" into "&q&" "&list
end sub 'part
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,932 ⟶ 3,277:
{{trans|Rexx}}
{{works with|Visual Basic .NET|2011}}
<langsyntaxhighlight lang="vbnet">' Partition an integer X into N primes - 29/03/2017
Option Explicit On
 
Line 2,011 ⟶ 3,356:
 
End Module 'PartitionIntoPrimes
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,024 ⟶ 3,369:
partition 22699 into 4 primes: 2+3+43+22651
partition 40355 into 3 primes: 3+139+40213
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
The relevant primes are generated here by a sieve.
<syntaxhighlight lang="wren">import "./math" for Int, Nums
import "./fmt" for Fmt
 
var primes = Int.primeSieve(1e5)
var foundCombo = false
 
var findCombo // recursive
findCombo = Fn.new { |k, x, m, n, combo|
if (k >= m) {
if (Nums.sum(combo.map { |i| primes[i] }.toList) == x) {
var s = (m > 1) ? "s" : ""
Fmt.write("Partitioned $5d with $2d prime$s: ", x, m, s)
for (i in 0...m) {
System.write(primes[combo[i]])
System.write((i < m - 1) ? "+" : "\n")
}
foundCombo = true
}
} else {
for (j in 0...n) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j
if (!foundCombo) findCombo.call(k + 1, x, m, n, combo)
}
}
}
}
 
var partition = Fn.new { |x, m|
if (x < 2 || m < 1 || m >= x) Fiber.abort("Invalid argument(s)")
var n = primes.where { |p| p <= x }.count
if (n < m) Fiber.abort("Not enough primes")
var combo = List.filled(m, 0)
foundCombo = false
findCombo.call(0, x, m, n, combo)
if (!foundCombo) {
var s = (m > 1) ? "s" : ""
Fmt.print("Partitioned $5d with $2d prime$s: (not possible)", x, m, s)
}
}
 
var a = [
[99809, 1],
[18, 2],
[19, 3],
[20, 4],
[2017, 24],
[22699, 1],
[22699, 2],
[22699, 3],
[22699, 4],
[40355, 3]
]
for (p in a) partition.call(p[0], p[1])</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|zkl}}==
Using the prime generator from task [[Extensible prime generator#zkl]].
<langsyntaxhighlight lang="zkl"> // Partition integer N into M unique primes
fcn partition(N,M,idx=0,ps=List()){
var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve);
Line 2,043 ⟶ 3,462:
}
Void // no solution
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">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));
}</langsyntaxhighlight>
{{out}}
<pre>
2,093

edits