Partition an integer x into n primes: Difference between revisions
(Added Factor) |
Not a robot (talk | contribs) (Add Cowgol) |
||
(52 intermediate revisions by 18 users not shown) | |||
Line 1: | Line 1: | ||
{{Task}} |
{{Task|Prime Numbers}} |
||
;Task: |
;Task: |
||
Line 11: | Line 11: | ||
Show in the output section the sum '''X''' and the '''N''' primes in ascending order separated by plus ('''+''') signs: |
Show in the output section the sum '''X''' and the '''N''' primes in ascending order separated by plus ('''+''') signs: |
||
<big> • </big> partition '''99809''' with 1 prime. |
|||
<big> • </big> partition '''18''' with 2 primes. |
|||
<big> • </big> partition '''19''' with 3 primes. |
|||
<big> • </big> partition '''20''' with 4 primes. |
|||
<big> • </big> partition '''2017''' with 24 primes. |
|||
<big> • </big> partition '''22699''' with 1, 2, 3, <u>and</u> 4 primes. |
|||
<big> • </big> partition '''40355''' with 3 primes. |
|||
The output could/should be shown in a format such as: |
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. |
::* Use any spacing that may be appropriate for the display. |
||
::* You need not validate the input(s). |
::* You need not validate the input(s). |
||
::* Use the lowest primes possible; use '''18 = 5+13''', not '''18 = 7+11'''. |
::* Use the lowest primes possible; use '''18 = 5+13''', not '''18 = 7+11'''. |
||
::* You only need to show one solution. |
::* You only need to show one solution. |
||
Line 41: | Line 41: | ||
:* [[Sequence of primes by trial division]] |
:* [[Sequence of primes by trial division]] |
||
<br><br> |
<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}} |
|||
<syntaxhighlight lang="c">#include <assert.h> |
|||
#include <stdbool.h> |
|||
#include <stdint.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
typedef struct bit_array_tag { |
|||
uint32_t size; |
|||
uint32_t* array; |
|||
} bit_array; |
|||
bool bit_array_create(bit_array* b, uint32_t size) { |
|||
uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t)); |
|||
if (array == NULL) |
|||
return false; |
|||
b->size = size; |
|||
b->array = array; |
|||
return true; |
|||
} |
|||
void bit_array_destroy(bit_array* b) { |
|||
free(b->array); |
|||
b->array = NULL; |
|||
} |
|||
void bit_array_set(bit_array* b, uint32_t index, bool value) { |
|||
assert(index < b->size); |
|||
uint32_t* p = &b->array[index >> 5]; |
|||
uint32_t bit = 1 << (index & 31); |
|||
if (value) |
|||
*p |= bit; |
|||
else |
|||
*p &= ~bit; |
|||
} |
|||
bool bit_array_get(const bit_array* b, uint32_t index) { |
|||
assert(index < b->size); |
|||
uint32_t bit = 1 << (index & 31); |
|||
return (b->array[index >> 5] & bit) != 0; |
|||
} |
|||
typedef struct sieve_tag { |
|||
uint32_t limit; |
|||
bit_array not_prime; |
|||
} sieve; |
|||
bool sieve_create(sieve* s, uint32_t limit) { |
|||
if (!bit_array_create(&s->not_prime, limit + 1)) |
|||
return false; |
|||
bit_array_set(&s->not_prime, 0, true); |
|||
bit_array_set(&s->not_prime, 1, true); |
|||
for (uint32_t p = 2; p * p <= limit; ++p) { |
|||
if (bit_array_get(&s->not_prime, p) == false) { |
|||
for (uint32_t q = p * p; q <= limit; q += p) |
|||
bit_array_set(&s->not_prime, q, true); |
|||
} |
|||
} |
|||
s->limit = limit; |
|||
return true; |
|||
} |
|||
void sieve_destroy(sieve* s) { |
|||
bit_array_destroy(&s->not_prime); |
|||
} |
|||
bool is_prime(const sieve* s, uint32_t n) { |
|||
assert(n <= s->limit); |
|||
return bit_array_get(&s->not_prime, n) == false; |
|||
} |
|||
bool find_prime_partition(const sieve* s, uint32_t number, uint32_t count, |
|||
uint32_t min_prime, uint32_t* p) { |
|||
if (count == 1) { |
|||
if (number >= min_prime && is_prime(s, number)) { |
|||
*p = number; |
|||
return true; |
|||
} |
|||
return false; |
|||
} |
|||
for (uint32_t prime = min_prime; prime < number; ++prime) { |
|||
if (!is_prime(s, prime)) |
|||
continue; |
|||
if (find_prime_partition(s, number - prime, count - 1, |
|||
prime + 1, p + 1)) { |
|||
*p = prime; |
|||
return true; |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
void print_prime_partition(const sieve* s, uint32_t number, uint32_t count) { |
|||
assert(count > 0); |
|||
uint32_t* primes = malloc(count * sizeof(uint32_t)); |
|||
if (primes == NULL) { |
|||
fprintf(stderr, "Out of memory\n"); |
|||
return; |
|||
} |
|||
if (!find_prime_partition(s, number, count, 2, primes)) { |
|||
printf("%u cannot be partitioned into %u primes.\n", number, count); |
|||
} else { |
|||
printf("%u = %u", number, primes[0]); |
|||
for (uint32_t i = 1; i < count; ++i) |
|||
printf(" + %u", primes[i]); |
|||
printf("\n"); |
|||
} |
|||
free(primes); |
|||
} |
|||
int main() { |
|||
const uint32_t limit = 100000; |
|||
sieve s = { 0 }; |
|||
if (!sieve_create(&s, limit)) { |
|||
fprintf(stderr, "Out of memory\n"); |
|||
return 1; |
|||
} |
|||
print_prime_partition(&s, 99809, 1); |
|||
print_prime_partition(&s, 18, 2); |
|||
print_prime_partition(&s, 19, 3); |
|||
print_prime_partition(&s, 20, 4); |
|||
print_prime_partition(&s, 2017, 24); |
|||
print_prime_partition(&s, 22699, 1); |
|||
print_prime_partition(&s, 22699, 2); |
|||
print_prime_partition(&s, 22699, 3); |
|||
print_prime_partition(&s, 22699, 4); |
|||
print_prime_partition(&s, 40355, 3); |
|||
sieve_destroy(&s); |
|||
return 0; |
|||
}</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|C sharp}}== |
=={{header|C sharp}}== |
||
{{works with|C sharp|7}} |
{{works with|C sharp|7}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections; |
using System.Collections; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 121: | Line 537: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 135: | Line 551: | ||
40355 with 3 primes: 3+139+40213 |
40355 with 3 primes: 3+139+40213 |
||
</pre> |
</pre> |
||
=={{header|C++}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="cpp">#include <algorithm> |
|||
#include <functional> |
|||
#include <iostream> |
|||
#include <vector> |
|||
std::vector<int> primes; |
|||
struct Seq { |
|||
public: |
|||
bool empty() { |
|||
return p < 0; |
|||
} |
|||
int front() { |
|||
return p; |
|||
} |
|||
void popFront() { |
|||
if (p == 2) { |
|||
p++; |
|||
} else { |
|||
p += 2; |
|||
while (!empty() && !isPrime(p)) { |
|||
p += 2; |
|||
} |
|||
} |
|||
} |
|||
private: |
|||
int p = 2; |
|||
bool isPrime(int n) { |
|||
if (n < 2) return false; |
|||
if (n % 2 == 0) return n == 2; |
|||
if (n % 3 == 0) return n == 3; |
|||
int d = 5; |
|||
while (d * d <= n) { |
|||
if (n % d == 0) return false; |
|||
d += 2; |
|||
if (n % d == 0) return false; |
|||
d += 4; |
|||
} |
|||
return true; |
|||
} |
|||
}; |
|||
// generate the first 50,000 primes and call it good |
|||
void init() { |
|||
Seq seq; |
|||
while (!seq.empty() && primes.size() < 50000) { |
|||
primes.push_back(seq.front()); |
|||
seq.popFront(); |
|||
} |
|||
} |
|||
bool findCombo(int k, int x, int m, int n, std::vector<int>& combo) { |
|||
if (k >= m) { |
|||
int sum = 0; |
|||
for (int idx : combo) { |
|||
sum += primes[idx]; |
|||
} |
|||
if (sum == x) { |
|||
auto word = (m > 1) ? "primes" : "prime"; |
|||
printf("Partitioned %5d with %2d %s ", x, m, word); |
|||
for (int idx = 0; idx < m; ++idx) { |
|||
std::cout << primes[combo[idx]]; |
|||
if (idx < m - 1) { |
|||
std::cout << '+'; |
|||
} else { |
|||
std::cout << '\n'; |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
} else { |
|||
for (int j = 0; j < n; j++) { |
|||
if (k == 0 || j > combo[k - 1]) { |
|||
combo[k] = j; |
|||
bool foundCombo = findCombo(k + 1, x, m, n, combo); |
|||
if (foundCombo) { |
|||
return true; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
void partition(int x, int m) { |
|||
if (x < 2 || m < 1 || m >= x) { |
|||
throw std::runtime_error("Invalid parameters"); |
|||
} |
|||
std::vector<int> filteredPrimes; |
|||
std::copy_if( |
|||
primes.cbegin(), primes.cend(), |
|||
std::back_inserter(filteredPrimes), |
|||
[x](int a) { return a <= x; } |
|||
); |
|||
int n = filteredPrimes.size(); |
|||
if (n < m) { |
|||
throw std::runtime_error("Not enough primes"); |
|||
} |
|||
std::vector<int> combo; |
|||
combo.resize(m); |
|||
if (!findCombo(0, x, m, n, combo)) { |
|||
auto word = (m > 1) ? "primes" : "prime"; |
|||
printf("Partitioned %5d with %2d %s: (not possible)\n", x, m, word); |
|||
} |
|||
} |
|||
int main() { |
|||
init(); |
|||
std::vector<std::pair<int, int>> a{ |
|||
{99809, 1}, |
|||
{ 18, 2}, |
|||
{ 19, 3}, |
|||
{ 20, 4}, |
|||
{ 2017, 24}, |
|||
{22699, 1}, |
|||
{22699, 2}, |
|||
{22699, 3}, |
|||
{22699, 4}, |
|||
{40355, 3} |
|||
}; |
|||
for (auto& p : a) { |
|||
partition(p.first, p.second); |
|||
} |
|||
return 0; |
|||
}</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|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}}== |
=={{header|D}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="d">import std.array : array; |
||
import std.range : take; |
import std.range : take; |
||
import std.stdio; |
import std.stdio; |
||
Line 254: | Line 1,073: | ||
partition(p[0], p[1]); |
partition(p[0], p[1]); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 270: | Line 1,089: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017 |
// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017 |
||
let rcTask n ng = |
let rcTask n ng = |
||
Line 280: | Line 1,099: | ||
|Some n->printfn "%d is the sum of %A" ng n |
|Some n->printfn "%d is the sum of %A" ng n |
||
|_ ->printfn "No Solution" |
|_ ->printfn "No Solution" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 296: | Line 1,115: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: formatting fry grouping kernel math.combinatorics |
||
math.parser math.primes sequences ; |
math.parser math.primes sequences ; |
||
Line 309: | Line 1,128: | ||
{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699 |
{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699 |
||
4 40355 3 } 2 group |
4 40355 3 } 2 group |
||
[ first2 2dup partition print-partition ] each</ |
[ first2 2dup partition print-partition ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 322: | Line 1,141: | ||
Partitioned 22699 with 4 primes: 2+3+43+22651 |
Partitioned 22699 with 4 primes: 2+3+43+22651 |
||
Partitioned 40355 with 3 primes: 3+139+40213 |
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> |
</pre> |
||
Line 327: | Line 1,350: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
... though uses a sieve to generate the relevant primes. |
... though uses a sieve to generate the relevant primes. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 438: | Line 1,461: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 455: | Line 1,478: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
<syntaxhighlight lang="haskell">import Data.List (delete, intercalate) |
|||
<lang haskell>{-# LANGUAGE TupleSections #-} |
|||
import Data.Numbers.Primes (primes) |
|||
import Data.Bool (bool) |
|||
-------------------- PRIME PARTITIONS --------------------- |
|||
import Data.List (delete, intercalate) |
|||
partitions :: Int -> Int -> [Int] |
|||
partitions x n |
|||
-- PRIME PARTITIONS ---------------------------------------------------------- |
|||
partition :: Int -> Int -> [Int] |
|||
partition x n |
|||
| n <= 1 = |
| n <= 1 = |
||
[ x |
[ x |
||
| |
| x == last ps ] |
||
| otherwise = |
| otherwise = go ps x n |
||
where |
where |
||
ps = takeWhile (<= x) primes |
ps = takeWhile (<= x) primes |
||
go ps_ x 1 = |
|||
[ x |
[ x |
||
| x `elem` ps_ ] |
| x `elem` ps_ ] |
||
go ps_ x n = ((flip bool [] . head) <*> null) (ps_ >>= found) |
|||
partition_ ps_ x n = |
|||
let found = foldMap partitionsFound ps_ |
|||
in nullOr found [] (head found) |
|||
where |
where |
||
found p = |
|||
((flip bool [] . return . (p :)) <*> null) |
|||
((go =<< delete p . flip takeWhile ps_ . (>=)) (x - p) (pred n)) |
|||
in nullOr rs [] [p : rs] |
|||
-------------------------- TEST --------------------------- |
|||
main :: IO () |
main :: IO () |
||
main = |
main = |
||
mapM_ putStrLn $ |
mapM_ putStrLn $ |
||
(\(x, n) -> |
(\(x, n) -> |
||
intercalate |
|||
" -> " |
|||
[ justifyLeft 9 ' ' (show (x, n)) |
|||
, let xs = partitions x n |
|||
in bool |
|||
in nullOr xs "(no solution)" (intercalate "+" (show <$> xs)) |
|||
(tail $ concatMap (('+' :) . show) xs) |
|||
"(no solution)" |
|||
(null xs) |
|||
]) <$> |
|||
concat |
concat |
||
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)] |
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)] |
||
, ( |
, (,) 22699 <$> [1 .. 4] |
||
, [(40355, 3)] |
, [(40355, 3)] |
||
] |
] |
||
------------------------- GENERIC ------------------------- |
|||
justifyLeft :: Int -> Char -> String -> String |
justifyLeft :: Int -> Char -> String -> String |
||
justifyLeft n c s = take n (s ++ replicate n c) |
justifyLeft n c s = take n (s ++ replicate n c)</syntaxhighlight> |
||
nullOr |
|||
:: Foldable t1 |
|||
=> t1 a -> t -> t -> t |
|||
nullOr 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</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>(99809,1) -> 99809 |
<pre>(99809,1) -> 99809 |
||
Line 544: | Line 1,536: | ||
=={{header|J}}== |
=={{header|J}}== |
||
<syntaxhighlight lang="j"> |
|||
<lang j> |
|||
load 'format/printf' |
load 'format/printf' |
||
Line 586: | Line 1,578: | ||
tests=: (99809 1) ; (18 2) ; (19 3) ; (20 4) ; (2017 24) ; (22699 1) ; (22699 2) ; (22699 3) ; (22699 4) |
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 |
(0&{ partitioned_in 1&{) each tests |
||
</syntaxhighlight> |
|||
</lang> |
|||
Line 605: | Line 1,597: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="java">import java.util.Arrays; |
||
import java.util.stream.IntStream; |
import java.util.stream.IntStream; |
||
Line 681: | Line 1,673: | ||
partition(40355, 3); |
partition(40355, 3); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Partitioned 99809 with 1 prime: 99809 |
<pre>Partitioned 99809 with 1 prime: 99809 |
||
Line 694: | Line 1,686: | ||
Partitioned 40355 with 3 primes: 3+139+40213</pre> |
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}}== |
=={{header|Julia}}== |
||
{{trans|Sidef}} |
{{trans|Sidef}} |
||
< |
<syntaxhighlight lang="julia">using Primes, Combinatorics |
||
function primepartition(x::Int64, n::Int64) |
function primepartition(x::Int64, n::Int64) |
||
Line 716: | Line 1,831: | ||
println("Partition of ", x, " into ", n, " primes: ", |
println("Partition of ", x, " into ", n, " primes: ", |
||
isempty(ans) ? "impossible" : join(ans, " + ")) |
isempty(ans) ? "impossible" : join(ans, " + ")) |
||
end</ |
end</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 734: | Line 1,849: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning |
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning |
||
Line 817: | Line 1,932: | ||
) |
) |
||
for (p in a) partition(p.first, p.second) |
for (p in a) partition(p.first, p.second) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 836: | Line 1,951: | ||
Using the prime generator class "sieve" from task [[Extensible prime generator#Lingo]]. |
Using the prime generator class "sieve" from task [[Extensible prime generator#Lingo]]. |
||
< |
<syntaxhighlight lang="lingo">---------------------------------------- |
||
-- returns a sorted list of the <cnt> smallest unique primes that add up to <n>, |
-- 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> |
-- or FALSE if there is no such partition of primes for <n> |
||
Line 890: | Line 2,005: | ||
delete char (str.length+1-delim.length) to str.length of str |
delete char (str.length+1-delim.length) to str.length of str |
||
return str |
return str |
||
end</ |
end</syntaxhighlight> |
||
< |
<syntaxhighlight lang="lingo">-- main |
||
_global.sieve = script("sieve").new() |
_global.sieve = script("sieve").new() |
||
Line 904: | Line 2,019: | ||
showPrimePartition(22699, 3) |
showPrimePartition(22699, 3) |
||
showPrimePartition(22699, 4) |
showPrimePartition(22699, 4) |
||
showPrimePartition(40355, 3)</ |
showPrimePartition(40355, 3)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 919: | Line 2,034: | ||
-- "Partitioned 40355 with 3 primes: 3+139+40213" |
-- "Partitioned 40355 with 3 primes: 3+139+40213" |
||
</pre> |
</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_}] := |
|||
With[ |
|||
{len = Length@list, nextHead = NestWhile[Drop[#, -1] &, list, Total[#] > target &]}, |
|||
Which[ |
|||
{} == nextHead, {{}, target}, |
|||
Total[nextHead] == target && Length@nextHead == len, {nextHead, target}, |
|||
True, {NestWhile[AppendPrime, MapAt[NextPrimeMemo, nextHead, -1], Length[#] < Length[list] &], target} |
|||
] |
|||
];(*This is the meat of the matter. If it determines that the job is impossible, it returns a structure with an empty list of summands. If the input satisfies the success criteria, it just returns it (this will be our fixed point). Otherwise, it generates a subsequent candidate.*) |
|||
FormatResult[{list_, number_}, targetCount_] := |
|||
StringForm[ |
|||
"Partitioned `1` with `2` prime`4`: `3`", |
|||
number, |
|||
targetCount, |
|||
If[0 == Length@list, "no solutions found", StringRiffle[list, "+"]], |
|||
If[1 == Length@list, "", "s"]]; (*Just a helper for pretty-printing the output*) |
|||
PrimePartition[number_, count_] := FixedPoint[NextCandidate, {PrimeList[count], number}];(*This is where things kick off. NextCandidate will eventually return the failure format or a success, and either of those are fixed points of the function.*) |
|||
TestCases = |
|||
{ |
|||
{99809, 1}, |
|||
{18, 2}, |
|||
{19, 3}, |
|||
{20, 4}, |
|||
{2017, 24}, |
|||
{22699, 1}, |
|||
{22699, 2}, |
|||
{22699, 3}, |
|||
{22699, 4}, |
|||
{40355, 3} |
|||
}; |
|||
TimedResults = ReleaseHold[Hold[AbsoluteTiming[FormatResult[PrimePartition @@ #, Last@#]]] & /@TestCases](*I thought it would be interesting to include the timings, which are in seconds*) |
|||
TimedResults // TableForm</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0.111699 Partitioned 99809 with 1 prime: 99809 |
|||
0.000407 Partitioned 18 with 2 primes: 5+13 |
|||
0.000346 Partitioned 19 with 3 primes: 3+5+11 |
|||
0.000765 Partitioned 20 with 4 primes: no solutions found |
|||
0.008381 Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 |
|||
0.028422 Partitioned 22699 with 1 prime: 22699 |
|||
0.02713 Partitioned 22699 with 2 primes: 2+22697 |
|||
20.207 Partitioned 22699 with 3 primes: 3+5+22691 |
|||
0.357536 Partitioned 22699 with 4 primes: 2+3+43+22651 |
|||
57.9928 Partitioned 40355 with 3 primes: 3+139+40213</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}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">partDistinctPrimes(x,n,mn=2)= |
||
{ |
{ |
||
if(n==1, return(if(isprime(x) && mn<=x, [x], 0))); |
if(n==1, return(if(isprime(x) && mn<=x, [x], 0))); |
||
Line 956: | Line 2,189: | ||
} |
} |
||
V=[[99809,1], [18,2], [19,3], [20,4], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]]; |
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]))</ |
for(i=1,#V, call(displayNicely, V[i]))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Partitioned 99809 with 1 prime: 99809 |
<pre>Partitioned 99809 with 1 prime: 99809 |
||
Line 972: | Line 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. |
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}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use ntheory ":all"; |
||
sub prime_partition { |
sub prime_partition { |
||
Line 986: | Line 2,219: | ||
my $partar = prime_partition(@$test); |
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"; |
printf "Partition %5d into %2d prime piece%s %s\n", $test->[0], $test->[1], ($test->[1] == 1) ? ": " : "s:", defined($partar) ? join("+",@$partar) : "not possible"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,002: | Line 2,235: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
{{works with|Rakudo|2018.02}} |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
<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> |
|||
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> |
|||
=={{header|Prolog}}== |
|||
<lang perl6>my @primes = lazy gather for 1 .. * { .take if $_.is-prime }; # lazy infinite list of primes |
|||
{{works with|SWI Prolog}} |
|||
<syntaxhighlight lang="prolog">prime_partition(N, 1, [N], Min):- |
|||
is_prime(N), |
|||
N > Min, |
|||
!. |
|||
prime_partition(N, K, [P|Rest], Min):- |
|||
K > 1, |
|||
is_prime(P), |
|||
P > Min, |
|||
P < N, |
|||
K1 is K - 1, |
|||
N1 is N - P, |
|||
prime_partition(N1, K1, Rest, P), |
|||
!. |
|||
prime_partition(N, K, Primes):- |
|||
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! [] } # short circuit for '1' partition |
|||
prime_partition(N, K, Primes, 1). |
|||
print_primes([Prime]):- |
|||
multi partition ( Int $number, Int $parts where * > 0 = 2 ) { |
|||
!, |
|||
my @these = @primes[ ^( @primes.first: * > $number, :k ) ]; |
|||
writef('%w\n', [Prime]). |
|||
for @these.combinations($parts) -> @this { return @this if @this.sum == $number } |
|||
print_primes([Prime|Primes]):- |
|||
[] |
|||
writef('%w + ', [Prime]), |
|||
} |
|||
print_primes(Primes). |
|||
print_prime_partition(N, K):- |
|||
# TESTING |
|||
prime_partition(N, K, Primes), |
|||
for 18,2, 19,3, 20,4, 99807,1, 99809,1, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3 |
|||
!, |
|||
-> $number, $parts { |
|||
writef('%w = ', [N]), |
|||
say (sprintf "Partition %5d into %2d prime piece", $number, $parts), |
|||
print_primes(Primes). |
|||
$parts == 1 ?? ': ' !! 's: ', (join '+', partition $number, $parts) || 'not possible' |
|||
print_prime_partition(N, K):- |
|||
}</lang> |
|||
writef('%w cannot be partitioned into %w primes.\n', [N, K]). |
|||
{{out}} |
|||
<pre>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</pre> |
|||
main:- |
|||
=={{header|Phix}}== |
|||
find_prime_numbers(100000), |
|||
Using is_prime(), primes[] and add_block() from [[Extensible_prime_generator#Phix]]. |
|||
print_prime_partition(99809, 1), |
|||
<lang Phix>function partition(integer v, n, idx=0) |
|||
print_prime_partition(18, 2), |
|||
if n=1 then |
|||
print_prime_partition(19, 3), |
|||
return iff(is_prime(v)?{v}:0) |
|||
print_prime_partition(20, 4), |
|||
end if |
|||
print_prime_partition(2017, 24), |
|||
object res |
|||
print_prime_partition(22699, 1), |
|||
while 1 do |
|||
print_prime_partition(22699, 2), |
|||
idx += 1 |
|||
print_prime_partition(22699, 3), |
|||
while length(primes)<idx do |
|||
print_prime_partition(22699, 4), |
|||
add_block() |
|||
print_prime_partition(40355, 3).</syntaxhighlight> |
|||
end while |
|||
integer np = primes[idx] |
|||
Module for finding prime numbers up to some limit: |
|||
if np>=floor(v/2) then exit end if |
|||
<syntaxhighlight lang="prolog">:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]). |
|||
res = partition(v-np, n-1, idx) |
|||
:- dynamic is_prime/1. |
|||
if sequence(res) then return np&res end if |
|||
end while |
|||
find_prime_numbers(N):- |
|||
return 0 |
|||
retractall(is_prime(_)), |
|||
end function |
|||
assertz(is_prime(2)), |
|||
init_sieve(N, 3), |
|||
sieve(N, 3). |
|||
init_sieve(N, P):- |
|||
P > N, |
|||
!. |
|||
init_sieve(N, P):- |
|||
assertz(is_prime(P)), |
|||
Q is P + 2, |
|||
init_sieve(N, Q). |
|||
sieve(N, P):- |
|||
P * P > N, |
|||
!. |
|||
sieve(N, P):- |
|||
is_prime(P), |
|||
!, |
|||
S is P * P, |
|||
cross_out(S, N, P), |
|||
Q is P + 2, |
|||
sieve(N, Q). |
|||
sieve(N, P):- |
|||
Q is P + 2, |
|||
sieve(N, Q). |
|||
cross_out(S, N, _):- |
|||
constant tests = {{99809, 1}, |
|||
S > N, |
|||
!. |
|||
{19, 3}, |
|||
cross_out(S, N, P):- |
|||
{20, 4}, |
|||
retract(is_prime(S)), |
|||
{2017, 24}, |
|||
!, |
|||
{22699, 1}, |
|||
Q is S + 2 * P, |
|||
cross_out(Q, N, P). |
|||
{22699, 3}, |
|||
cross_out(S, N, P):- |
|||
{22699, 4}, |
|||
Q is S + 2 * P, |
|||
cross_out(Q, N, P).</syntaxhighlight> |
|||
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</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<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> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
<syntaxhighlight lang="python">from itertools import combinations as cmb |
|||
<lang Python> |
|||
from itertools import combinations as cmb |
|||
def isP(n): |
def isP(n): |
||
if n==2: |
if n == 2: |
||
return True |
return True |
||
if n%2==0: |
if n % 2 == 0: |
||
return False |
return False |
||
return all(n%x>0 for x in range(3, int(n**0.5)+1, 2)) |
return all(n % x > 0 for x in range(3, int(n ** 0.5) + 1, 2)) |
||
def genP(n): |
def genP(n): |
||
p = [2] |
p = [2] |
||
p.extend([x for x in range(3, n+1, 2) if isP(x)]) |
p.extend([x for x in range(3, n + 1, 2) if isP(x)]) |
||
return p |
return p |
||
data = [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24), (22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)] |
|||
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: |
for n, cnt in data: |
||
ci = iter(cmb(genP(n), cnt)) |
ci = iter(cmb(genP(n), cnt)) |
||
while True: |
while True: |
||
try: |
try: |
||
c = next(ci) |
c = next(ci) |
||
if sum(c)==n: |
if sum(c) == n: |
||
print( |
print(' '.join( |
||
[repr((n, cnt)), "->", '+'.join(str(s) for s in c)] |
|||
)) |
|||
break |
break |
||
except: |
except StopIteration: |
||
print(n, |
print(repr((n, cnt)) + " -> Not possible") |
||
break |
break</syntaxhighlight> |
||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre>(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 |
|||
20 , 4 -> Not possible |
|||
(22699, 1) -> 22699 |
|||
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 |
(22699, 2) -> 2+22697 |
||
22699 |
(22699, 3) -> 3+5+22691 |
||
22699 |
(22699, 4) -> 2+3+43+22651 |
||
(40355, 3) -> 3+139+40213</pre> |
|||
40355 , 3 -> 3+139+40213 |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require math/number-theory) |
(require math/number-theory) |
||
Line 1,162: | Line 2,474: | ||
(report-partition 22699 3) |
(report-partition 22699 3) |
||
(report-partition 22699 4) |
(report-partition 22699 4) |
||
(report-partition 40355 3))</ |
(report-partition 40355 3))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,177: | Line 2,489: | ||
partition 40355 with 3 primes: 3 + 139 + 40213</pre> |
partition 40355 with 3 primes: 3 + 139 + 40213</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2018.10}} |
|||
<syntaxhighlight lang="raku" line>use Math::Primesieve; |
|||
my $sieve = Math::Primesieve.new; |
|||
# short circuit for '1' partition |
|||
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! () } |
|||
multi partition ( Int $number, Int $parts where * > 0 = 2 ) { |
|||
my @these = $sieve.primes($number); |
|||
for @these.combinations($parts) { .return if .sum == $number }; |
|||
() |
|||
} |
|||
# TESTING |
|||
(18,2, 19,3, 20,4, 99807,1, 99809,1, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3)\ |
|||
.race(:1batch).map: -> $number, $parts { |
|||
say (sprintf "Partition %5d into %2d prime piece", $number, $parts), |
|||
$parts == 1 ?? ': ' !! 's: ', join '+', partition($number, $parts) || 'not possible' |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</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}}== |
=={{header|REXX}}== |
||
Usage note: entering ranges of '''X''' and '''N''' numbers (arguments) from the command line: |
Usage note: entering ranges of '''X''' and '''N''' numbers (arguments) from the command line: |
||
Line 1,183: | Line 2,608: | ||
which means: partition all integers (inclusive) from '''X''' ──► '''Y''' with '''N''' ──► '''M''' primes. |
which means: partition all integers (inclusive) from '''X''' ──► '''Y''' with '''N''' ──► '''M''' primes. |
||
<br>The ''to'' number ('''Y''' or '''M''') can be omitted. |
<br>The ''to'' number ('''Y''' or '''M''') can be omitted. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program partitions integer(s) (greater than unity) into N primes. */ |
||
parse arg what /*obtain an optional list from the C.L.*/ |
parse arg what /*obtain an optional list from the C.L.*/ |
||
do until what=='' /*possibly process a series of integers*/ |
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 what x n what; parse var x x '-' y /*get possible range and # partitions.*/ |
||
parse var n n '-' m /* |
parse var n n '-' m /* " " " " " " */ |
||
if x=='' | x=="," then x= |
if x=='' | x=="," then x= 19 /*Not specified? Then use the default.*/ |
||
if y=='' | y=="," then y= |
if y=='' | y=="," then y= x /* " " " " " " */ |
||
if n=='' | n=="," then n= |
if n=='' | n=="," then n= 3 /* " " " " " " */ |
||
if m=='' | m=="," then m= |
if m=='' | m=="," then m= n /* " " " " " " */ |
||
call genP y /*generate Y number of primes. */ |
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 |
do q=n to m; call part /* " G into Q primes. */ |
||
end /*q*/ |
|||
end /*g*/ |
|||
end /*until*/ |
end /*until*/ |
||
exit 0 /*stick a fork in it, we're all done. */ |
exit 0 /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
genP: arg high; @.1=2; |
genP: arg high; @.1= 2; @.2= 3; #= 2 /*get highest prime, assign some vars. */ |
||
do j=@.#+2 by 2 until @.#>high /*only find odd primes from here on. */ |
do j=@.#+2 by 2 until @.#>high /*only find odd primes from here on. */ |
||
do k=2 while k*k<=j /*divide by some known low odd primes. */ |
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.*/ |
if j // @.k==0 then iterate j /*Is J divisible by P? Then ¬ prime.*/ |
||
end /*k*/ /* [↓] a prime (J) has been found. */ |
end /*k*/ /* [↓] a prime (J) has been found. */ |
||
#=#+1; |
#= # + 1; @.#= j /*bump prime count; assign prime to @.*/ |
||
end /*j*/ |
end /*j*/; return |
||
return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
getP: procedure expose i. p. @.; parse arg z /*bump the prime in the partition list.*/ |
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 |
if i.z==0 then do; _= z - 1; i.z= i._; end |
||
i.z=i.z+1; _=i.z; p.z=@._; return 0 |
i.z= i.z + 1; _= i.z; p.z= @._; return 0 |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
list: _=p.1; if $==g then |
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; |
part: i.= 0; do j=1 for q; call getP j |
||
end /*j*/ |
|||
do s=1 for q; $=$+p.s /* [↓] is sum of the primes too large?*/ |
|||
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*/ |
|||
end |
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.*/ |
|||
return</lang> |
|||
say 'partitioned' center(g,9) "into" center(q, 5) list() |
|||
return</syntaxhighlight> |
|||
{{out|output|text= when using the input of: <tt> 99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 </tt>}} |
{{out|output|text= when using the input of: <tt> 99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 </tt>}} |
||
<pre> |
<pre> |
||
Line 1,244: | Line 2,675: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Partition an integer X into N primes |
# Project : Partition an integer X into N primes |
||
Line 1,316: | Line 2,747: | ||
next |
next |
||
return items |
return items |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 1,332: | Line 2,763: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require "prime" |
||
def prime_partition(x, n) |
def prime_partition(x, n) |
||
Line 1,346: | Line 2,777: | ||
puts "Partitioned #{prime} with #{num} primes: #{str}" |
puts "Partitioned #{prime} with #{num} primes: #{str}" |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Partitioned 99809 with 1 primes: 99809 |
<pre>Partitioned 99809 with 1 primes: 99809 |
||
Line 1,359: | Line 2,790: | ||
Partitioned 40355 with 3 primes: 3 + 139 + 40213 |
Partitioned 40355 with 3 primes: 3 + 139 + 40213 |
||
</pre> |
</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}}== |
|||
<syntaxhighlight lang="scala">object PartitionInteger { |
|||
def sieve(nums: LazyList[Int]): LazyList[Int] = |
|||
LazyList.cons(nums.head, sieve((nums.tail) filter (_ % nums.head != 0))) |
|||
// An 'infinite' stream of primes, lazy evaluation and memo-ized |
|||
private val oddPrimes = sieve(LazyList.from(3, 2)) |
|||
private val primes = sieve(2 #:: oddPrimes).take(3600 /*50_000*/) |
|||
private def findCombo(k: Int, x: Int, m: Int, n: Int, combo: Array[Int]): Boolean = { |
|||
var foundCombo = combo.map(i => primes(i)).sum == x |
|||
if (k >= m) { |
|||
if (foundCombo) { |
|||
val s: String = if (m > 1) "s" else "" |
|||
printf("Partitioned %5d with %2d prime%s: ", x, m, s) |
|||
for (i <- 0 until m) { |
|||
print(primes(combo(i))) |
|||
if (i < m - 1) print('+') else println() |
|||
} |
|||
} |
|||
} else for (j <- 0 until n if k == 0 || j > combo(k - 1)) { |
|||
combo(k) = j |
|||
if (!foundCombo) foundCombo = findCombo(k + 1, x, m, n, combo) |
|||
} |
|||
foundCombo |
|||
} |
|||
private def partition(x: Int, m: Int): Unit = { |
|||
val n: Int = primes.count(it => it <= x) |
|||
if (n < m) throw new IllegalArgumentException("Not enough primes") |
|||
if (!findCombo(0, x, m, n, new Array[Int](m))) |
|||
printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, if (m > 1) "s" else " ") |
|||
} |
|||
def main(args: Array[String]): Unit = { |
|||
partition(99809, 1) |
|||
partition(18, 2) |
|||
partition(19, 3) |
|||
partition(20, 4) |
|||
partition(2017, 24) |
|||
partition(22699, 1) |
|||
partition(22699, 2) |
|||
partition(22699, 3) |
|||
partition(22699, 4) |
|||
partition(40355, 3) |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{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}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="ruby">func prime_partition(num, parts) { |
||
if (parts == 1) { |
if (parts == 1) { |
||
Line 1,385: | Line 3,059: | ||
say ("Partition %5d into %2d prime piece" % (num, parts), |
say ("Partition %5d into %2d prime piece" % (num, parts), |
||
parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible') |
parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible') |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Partition 18 into 2 prime pieces: 5+13 |
|||
<pre> |
|||
Partition 18 into 2 prime pieces: 5+13 |
|||
Partition 19 into 3 prime pieces: 3+5+11 |
Partition 19 into 3 prime pieces: 3+5+11 |
||
Partition 20 into 4 prime pieces: not possible |
Partition 20 into 4 prime pieces: not possible |
||
Line 1,398: | Line 3,071: | ||
Partition 22699 into 3 prime pieces: 3+5+22691 |
Partition 22699 into 3 prime pieces: 3+5+22691 |
||
Partition 22699 into 4 prime pieces: 2+3+43+22651 |
Partition 22699 into 4 prime pieces: 2+3+43+22651 |
||
Partition 40355 into 3 prime pieces: 3+139+40213 |
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> |
</pre> |
||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
{{trans|Rexx}} |
{{trans|Rexx}} |
||
< |
<syntaxhighlight lang="vb">' Partition an integer X into N primes |
||
dim p(),a(32),b(32),v,g: redim p(64) |
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" |
what="99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 3" |
||
Line 1,466: | Line 3,259: | ||
wscript.echo "partition "&g&" into "&q&" "&list |
wscript.echo "partition "&g&" into "&q&" "&list |
||
end sub 'part |
end sub 'part |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,484: | Line 3,277: | ||
{{trans|Rexx}} |
{{trans|Rexx}} |
||
{{works with|Visual Basic .NET|2011}} |
{{works with|Visual Basic .NET|2011}} |
||
< |
<syntaxhighlight lang="vbnet">' Partition an integer X into N primes - 29/03/2017 |
||
Option Explicit On |
Option Explicit On |
||
Line 1,563: | Line 3,356: | ||
End Module 'PartitionIntoPrimes |
End Module 'PartitionIntoPrimes |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,578: | Line 3,371: | ||
</pre> |
</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}}== |
=={{header|zkl}}== |
||
Using the prime generator from task [[Extensible prime generator#zkl]]. |
Using the prime generator from task [[Extensible prime generator#zkl]]. |
||
< |
<syntaxhighlight lang="zkl"> // Partition integer N into M unique primes |
||
fcn partition(N,M,idx=0,ps=List()){ |
fcn partition(N,M,idx=0,ps=List()){ |
||
var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve); |
var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve); |
||
Line 1,596: | Line 3,462: | ||
} |
} |
||
Void // no solution |
Void // no solution |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight 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), )){ |
T(22699,1),T(22699,2),T(22699,3),T(22699,4),T(40355,3), )){ |
||
ps:=partition(n,m); |
ps:=partition(n,m); |
||
if(ps) println("Partition %d with %d prime(s): %s".fmt(n,m,ps.concat("+"))); |
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)); |
else println("Can not partition %d with %d prime(s)".fmt(n,m)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 09:48, 10 April 2024
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Partition a positive integer X into N distinct primes.
Or, to put it in another way:
Find N unique primes such that they add up to X.
Show in the output section the sum X and the N primes in ascending order separated by plus (+) signs:
• partition 99809 with 1 prime. • partition 18 with 2 primes. • partition 19 with 3 primes. • partition 20 with 4 primes. • partition 2017 with 24 primes. • partition 22699 with 1, 2, 3, and 4 primes. • partition 40355 with 3 primes.
The output could/should be shown in a format such as:
Partitioned 19 with 3 primes: 3+5+11
- Use any spacing that may be appropriate for the display.
- You need not validate the input(s).
- Use the lowest primes possible; use 18 = 5+13, not 18 = 7+11.
- You only need to show one solution.
This task is similar to factoring an integer.
- Related tasks
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)
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
ALGOL 68
BEGIN # find the lowest n distinct primes that sum to an integer x #
INT max number = 100 000; # largest number we will consider #
# sieve the primes to max number #
[ 1 : max number ]BOOL prime; FOR i TO UPB prime DO prime[ i ] := ODD i OD;
prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR s FROM 3 BY 2 TO ENTIER sqrt( max number ) DO
IF prime[ s ] THEN
FOR p FROM s * s BY s TO UPB prime DO prime[ p ] := FALSE OD
FI
OD;
[ 1 : 0 ]INT no partition; # empty array - used if can't partition #
# returns n partitioned into p primes or an empty array if n can't be #
# partitioned into p primes, the first prime to try is in start #
PROC partition from = ( INT n, p, start )[]INT:
IF p < 1 OR n < 2 OR start < 2 THEN # invalid parameters #
no partition
ELIF p = 1 THEN # partition into 1 prime - n must be prime #
IF NOT prime[ n ] THEN no partition ELSE n FI
ELIF p = 2 THEN # partition into a pair of primes #
INT half n = n OVER 2;
INT p1 := 0, p2 := 0;
BOOL found := FALSE;
FOR p pos FROM start TO UPB prime WHILE NOT found AND p pos < half n DO
IF prime[ p pos ] THEN
p1 := p pos;
p2 := n - p pos;
found := prime[ p2 ]
FI
OD;
IF NOT found THEN no partition ELSE ( p1, p2 ) FI
ELSE # partition into 3 or more primes #
[ 1 : p ]INT p2;
INT half n = n OVER 2;
INT p1 := 0;
BOOL found := FALSE;
FOR p pos FROM start TO UPB prime WHILE NOT found AND p pos < half n DO
IF prime[ p pos ] THEN
p1 := p pos;
[]INT sub partition = partition from( n - p1, p - 1, p pos + 1 );
IF found := UPB sub partition = p - 1 THEN
# have p - 1 primes summing to n - p1 #
p2[ 1 ] := p1;
p2[ 2 : p ] := sub partition
FI
FI
OD;
IF NOT found THEN no partition ELSE p2 FI
FI # partition from # ;
# returns the partition of n into p primes or an empty array if that is #
# not possible #
PROC partition = ( INT n, p )[]INT: partition from( n, p, 2 );
# show the first partition of n into p primes, if that is possible #
PROC show partition = ( INT n, p )VOID:
BEGIN
[]INT primes = partition( n, p );
STRING partition info = whole( n, -6 ) + " with " + whole( p, -2 )
+ " prime" + IF p = 1 THEN " " ELSE "s" FI + ": ";
IF UPB primes < LWB primes THEN
print( ( "Partitioning ", partition info, "is not possible" ) )
ELSE
print( ( "Partitioned ", partition info ) );
print( ( whole( primes[ LWB primes ], 0 ) ) );
FOR p pos FROM LWB primes + 1 TO UPB primes DO
print( ( "+", whole( primes[ p pos ], 0 ) ) )
OD
FI;
print( ( newline ) )
END # show partition # ;
# test cases #
show partition( 99809, 1 );
show partition( 18, 2 );
show partition( 19, 3 );
show partition( 20, 4 );
show partition( 2017, 24 );
show partition( 22699, 1 );
show partition( 22699, 2 );
show partition( 22699, 3 );
show partition( 22699, 4 );
show partition( 40355, 3 )
END
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioning 20 with 4 primes: is not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
APL
primepart←{
sieve←{
(⊃{0@(1↓⍺×⍳⌊(⍴⍵)÷⍺)⊢⍵}/(1↓⍳⍵),⊂(0,1↓⍵/1))/⍳⍵
}
part←{
0=⍴⍺⍺:⍬
⍵=1:(⍺⍺=⍺)/⍺⍺
0≠⍴r←(⍺-⊃⍺⍺)((1↓⍺⍺)∇∇)⍵-1:(⊃⍺⍺),r
⍺((1↓⍺⍺)∇∇)⍵
}
⍺((sieve ⍺)part)⍵
}
primepart_test←{
tests←(99809 1)(18 2)(19 3)(20 4)(2017 24)
tests,←(22699 1)(22699 2)(22699 3)(22699 4)(40355 3)
{
x n←⍵
p←x primepart n
⍞←'Partition ',(⍕x),' with ',(⍕n),' primes: '
0=⍴p:⍞←'not possible.',⎕TC[2]
⍞←(1↓∊'+',¨⍕¨p),⎕TC[2]
}¨tests
}
- Output:
primepart_test⍬ Partition 99809 with 1 primes: 99809 Partition 18 with 2 primes: 5+13 Partition 19 with 3 primes: 3+5+11 Partition 20 with 4 primes: not possible. Partition 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 with 1 primes: 22699 Partition 22699 with 2 primes: 2+22697 Partition 22699 with 3 primes: 3+5+22691 Partition 22699 with 4 primes: 2+3+43+22651 Partition 40355 with 3 primes: 3+139+40213
BCPL
get "libhdr"
let sieve(n, prime) be
$( let i = 2
0!prime := false
1!prime := false
for i = 2 to n do i!prime := true
while i*i <= n
$( let j = i*i
while j <= n
$( j!prime := false
j := j+i
$)
i := i+1
$)
$)
let partition(x, n, prime, p, part) =
p > x -> false,
n = 1 -> valof $( !part := x; resultis x!prime $),
valof
$( p := p+1 repeatuntil p!prime
!part := p
if partition(x-p, n-1, prime, p, part+1) resultis true
resultis partition(x, n, prime, p, part)
$)
let showpart(n, part) be
$( writef("%N", !part)
unless n=1 do
$( wrch('+')
showpart(n-1, part+1)
$)
$)
let show(x, n, prime) be
$( let part = vec 32
writef("Partitioned %N with %N prime%S: ", x, n, n=1->"", "s")
test partition(x, n, prime, 1, part)
do showpart(n, part)
or writes("not possible")
newline()
$)
let start() be
$( let prime = getvec(100000)
let tests = table 99809,1, 18,2, 19,3, 20,4, 2017,24,
22699,1, 22699,2, 22699,3, 22699,4, 40355,3
sieve(100000, prime)
for t = 0 to 9 do show(tests!(t*2), tests!(t*2+1), prime)
freevec(prime)
$)
- Output:
Partitioned 99809 with 1 prime: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
C
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct bit_array_tag {
uint32_t size;
uint32_t* array;
} bit_array;
bool bit_array_create(bit_array* b, uint32_t size) {
uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t));
if (array == NULL)
return false;
b->size = size;
b->array = array;
return true;
}
void bit_array_destroy(bit_array* b) {
free(b->array);
b->array = NULL;
}
void bit_array_set(bit_array* b, uint32_t index, bool value) {
assert(index < b->size);
uint32_t* p = &b->array[index >> 5];
uint32_t bit = 1 << (index & 31);
if (value)
*p |= bit;
else
*p &= ~bit;
}
bool bit_array_get(const bit_array* b, uint32_t index) {
assert(index < b->size);
uint32_t bit = 1 << (index & 31);
return (b->array[index >> 5] & bit) != 0;
}
typedef struct sieve_tag {
uint32_t limit;
bit_array not_prime;
} sieve;
bool sieve_create(sieve* s, uint32_t limit) {
if (!bit_array_create(&s->not_prime, limit + 1))
return false;
bit_array_set(&s->not_prime, 0, true);
bit_array_set(&s->not_prime, 1, true);
for (uint32_t p = 2; p * p <= limit; ++p) {
if (bit_array_get(&s->not_prime, p) == false) {
for (uint32_t q = p * p; q <= limit; q += p)
bit_array_set(&s->not_prime, q, true);
}
}
s->limit = limit;
return true;
}
void sieve_destroy(sieve* s) {
bit_array_destroy(&s->not_prime);
}
bool is_prime(const sieve* s, uint32_t n) {
assert(n <= s->limit);
return bit_array_get(&s->not_prime, n) == false;
}
bool find_prime_partition(const sieve* s, uint32_t number, uint32_t count,
uint32_t min_prime, uint32_t* p) {
if (count == 1) {
if (number >= min_prime && is_prime(s, number)) {
*p = number;
return true;
}
return false;
}
for (uint32_t prime = min_prime; prime < number; ++prime) {
if (!is_prime(s, prime))
continue;
if (find_prime_partition(s, number - prime, count - 1,
prime + 1, p + 1)) {
*p = prime;
return true;
}
}
return false;
}
void print_prime_partition(const sieve* s, uint32_t number, uint32_t count) {
assert(count > 0);
uint32_t* primes = malloc(count * sizeof(uint32_t));
if (primes == NULL) {
fprintf(stderr, "Out of memory\n");
return;
}
if (!find_prime_partition(s, number, count, 2, primes)) {
printf("%u cannot be partitioned into %u primes.\n", number, count);
} else {
printf("%u = %u", number, primes[0]);
for (uint32_t i = 1; i < count; ++i)
printf(" + %u", primes[i]);
printf("\n");
}
free(primes);
}
int main() {
const uint32_t limit = 100000;
sieve s = { 0 };
if (!sieve_create(&s, limit)) {
fprintf(stderr, "Out of memory\n");
return 1;
}
print_prime_partition(&s, 99809, 1);
print_prime_partition(&s, 18, 2);
print_prime_partition(&s, 19, 3);
print_prime_partition(&s, 20, 4);
print_prime_partition(&s, 2017, 24);
print_prime_partition(&s, 22699, 1);
print_prime_partition(&s, 22699, 2);
print_prime_partition(&s, 22699, 3);
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
sieve_destroy(&s);
return 0;
}
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
C#
using System;
using System.Collections;
using System.Collections.Generic;
using static System.Linq.Enumerable;
public static class Rosetta
{
static void Main()
{
foreach ((int x, int n) in new [] {
(99809, 1),
(18, 2),
(19, 3),
(20, 4),
(2017, 24),
(22699, 1),
(22699, 2),
(22699, 3),
(22699, 4),
(40355, 3)
}) {
Console.WriteLine(Partition(x, n));
}
}
public static string Partition(int x, int n) {
if (x < 1 || n < 1) throw new ArgumentOutOfRangeException("Parameters must be positive.");
string header = $"{x} with {n} {(n == 1 ? "prime" : "primes")}: ";
int[] primes = SievePrimes(x).ToArray();
if (primes.Length < n) return header + "not enough primes";
int[] solution = CombinationsOf(n, primes).FirstOrDefault(c => c.Sum() == x);
return header + (solution == null ? "not possible" : string.Join("+", solution);
}
static IEnumerable<int> SievePrimes(int bound) {
if (bound < 2) yield break;
yield return 2;
BitArray composite = new BitArray((bound - 1) / 2);
int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
for (int i = 0; i < limit; i++) {
if (composite[i]) continue;
int prime = 2 * i + 3;
yield return prime;
for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime) composite[j] = true;
}
for (int i = limit; i < composite.Count; i++) {
if (!composite[i]) yield return 2 * i + 3;
}
}
static IEnumerable<int[]> CombinationsOf(int count, int[] input) {
T[] result = new T[count];
foreach (int[] indices in Combinations(input.Length, count)) {
for (int i = 0; i < count; i++) result[i] = input[indices[i]];
yield return result;
}
}
static IEnumerable<int[]> Combinations(int n, int k) {
var result = new int[k];
var stack = new Stack<int>();
stack.Push(0);
while (stack.Count > 0) {
int index = stack.Count - 1;
int value = stack.Pop();
while (value < n) {
result[index++] = value++;
stack.Push(value);
if (index == k) {
yield return result;
break;
}
}
}
}
}
- Output:
99809 with 1 prime: 99809 18 with 2 primes: 5+13 19 with 3 primes: 3+5+11 20 with 4 primes: not possible 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 22699 with 1 prime: 22699 22699 with 2 primes: 2+22697 22699 with 3 primes: 3+5+22691 22699 with 4 primes: 2+3+43+22651 40355 with 3 primes: 3+139+40213
C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
std::vector<int> primes;
struct Seq {
public:
bool empty() {
return p < 0;
}
int front() {
return p;
}
void popFront() {
if (p == 2) {
p++;
} else {
p += 2;
while (!empty() && !isPrime(p)) {
p += 2;
}
}
}
private:
int p = 2;
bool isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
};
// generate the first 50,000 primes and call it good
void init() {
Seq seq;
while (!seq.empty() && primes.size() < 50000) {
primes.push_back(seq.front());
seq.popFront();
}
}
bool findCombo(int k, int x, int m, int n, std::vector<int>& combo) {
if (k >= m) {
int sum = 0;
for (int idx : combo) {
sum += primes[idx];
}
if (sum == x) {
auto word = (m > 1) ? "primes" : "prime";
printf("Partitioned %5d with %2d %s ", x, m, word);
for (int idx = 0; idx < m; ++idx) {
std::cout << primes[combo[idx]];
if (idx < m - 1) {
std::cout << '+';
} else {
std::cout << '\n';
}
}
return true;
}
} else {
for (int j = 0; j < n; j++) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j;
bool foundCombo = findCombo(k + 1, x, m, n, combo);
if (foundCombo) {
return true;
}
}
}
}
return false;
}
void partition(int x, int m) {
if (x < 2 || m < 1 || m >= x) {
throw std::runtime_error("Invalid parameters");
}
std::vector<int> filteredPrimes;
std::copy_if(
primes.cbegin(), primes.cend(),
std::back_inserter(filteredPrimes),
[x](int a) { return a <= x; }
);
int n = filteredPrimes.size();
if (n < m) {
throw std::runtime_error("Not enough primes");
}
std::vector<int> combo;
combo.resize(m);
if (!findCombo(0, x, m, n, combo)) {
auto word = (m > 1) ? "primes" : "prime";
printf("Partitioned %5d with %2d %s: (not possible)\n", x, m, word);
}
}
int main() {
init();
std::vector<std::pair<int, int>> a{
{99809, 1},
{ 18, 2},
{ 19, 3},
{ 20, 4},
{ 2017, 24},
{22699, 1},
{22699, 2},
{22699, 3},
{22699, 4},
{40355, 3}
};
for (auto& p : a) {
partition(p.first, p.second);
}
return 0;
}
- Output:
Partitioned 99809 with 1 prime 99809 Partitioned 18 with 2 primes 5+13 Partitioned 19 with 3 primes 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime 22699 Partitioned 22699 with 2 primes 2+22697 Partitioned 22699 with 3 primes 3+5+22691 Partitioned 22699 with 4 primes 2+3+43+22651 Partitioned 40355 with 3 primes 3+139+40213
CLU
isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0 = 0 then return(s) end
x1: int := (x0 + s/x0) / 2
while x1 < x0 do
x0, x1 := x1, (x0 + s/x0) / 2
end
return(x0)
end isqrt
primes = proc (n: int) returns (sequence[int])
prime: array[bool] := array[bool]$fill(1, n, true)
prime[1] := false
for p: int in int$from_to(2, isqrt(n)) do
for c: int in int$from_to_by(p*p, n, p) do
prime[c] := false
end
end
pr: array[int] := array[int]$predict(1, n)
for p: int in array[bool]$indexes(prime) do
if prime[p] then array[int]$addh(pr, p) end
end
return(sequence[int]$a2s(pr))
end primes
partition_sum = proc (x, n: int, nums: sequence[int])
returns (sequence[int])
signals (impossible)
if n<=0 cor sequence[int]$empty(nums) then signal impossible end
if n=1 then
for k: int in sequence[int]$elements(nums) do
if x=k then return(sequence[int]$[x]) end
end
signal impossible
end
k: int := sequence[int]$bottom(nums)
rest: sequence[int] := sequence[int]$reml(nums)
return(sequence[int]$addl(partition_sum(x-k, n-1, rest), k))
except when impossible:
return(partition_sum(x, n, rest))
resignal impossible
end
end partition_sum
prime_partition = proc (x, n: int)
returns (sequence[int])
signals (impossible)
return(partition_sum(x, n, primes(x))) resignal impossible
end prime_partition
format_sum = proc (nums: sequence[int]) returns (string)
result: string := ""
for n: int in sequence[int]$elements(nums) do
result := result || "+" || int$unparse(n)
end
return(string$rest(result, 2))
end format_sum
start_up = proc ()
test = struct[x: int, n: int]
tests: sequence[test] := sequence[test]$[
test${x:99809,n:1}, test${x:18,n:2}, test${x:19,n:3}, test${x:20,n:4},
test${x:2017,n:24}, test${x:22699,n:1}, test${x:22699,n:2},
test${x:22699,n:3}, test${x:22699,n:4}, test${x:40355,n:3}
]
po: stream := stream$primary_output()
for t: test in sequence[test]$elements(tests) do
stream$puts(po, "Partitioned " || int$unparse(t.x) || " with "
|| int$unparse(t.n) || " primes: ")
stream$putl(po, format_sum(prime_partition(t.x, t.n)))
except when impossible:
stream$putl(po, "not possible.")
end
end
end start_up
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible. Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Cowgol
include "cowgol.coh";
const MAXPRIM := 100000;
const MAXPRIM_B := (MAXPRIM >> 3) + 1;
var primebits: uint8[MAXPRIM_B];
typedef ENTRY_T is @indexof primebits;
sub pentry(n: uint32): (ent: ENTRY_T, bit: uint8) is
ent := (n >> 3) as ENTRY_T;
bit := (n & 7) as uint8;
end sub;
sub setprime(n: uint32, prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
var one: uint8 := 1;
primebits[ent] := primebits[ent] & ~(one << bit);
primebits[ent] := primebits[ent] | (prime << bit);
end sub;
sub prime(n: uint32): (prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
prime := (primebits[ent] >> bit) & 1;
end sub;
sub sieve() is
MemSet(&primebits[0], 0xFF, @bytesof primebits);
setprime(0, 0);
setprime(1, 0);
var p: uint32 := 2;
while p*p <= MAXPRIM loop
var c := p*p;
while c <= MAXPRIM loop
setprime(c, 0);
c := c + p;
end loop;
p := p + 1;
end loop;
end sub;
sub nextprime(p: uint32): (r: uint32) is
r := p;
loop
r := r + 1;
if prime(r) != 0 then break; end if;
end loop;
end sub;
sub partition(x: uint32, n: uint8, part: [uint32]): (r: uint8) is
record State is
x: uint32;
n: uint8;
p: uint32;
part: [uint32];
end record;
var stack: State[128];
var sp: @indexof stack := 0;
sub Push(x: uint32, n: uint8, p: uint32, part: [uint32]) is
stack[sp].x := x;
stack[sp].n := n;
stack[sp].p := p;
stack[sp].part := part;
sp := sp + 1;
end sub;
sub Pull(): (x: uint32, n: uint8, p: uint32, part: [uint32]) is
sp := sp - 1;
x := stack[sp].x;
n := stack[sp].n;
p := stack[sp].p;
part := stack[sp].part;
end sub;
r := 0;
Push(x, n, 1, part);
while sp > 0 loop
var p: uint32;
(x, n, p, part) := Pull();
p := nextprime(p);
if x < p then
continue;
end if;
if n == 1 then
if prime(x) != 0 then
r := 1;
[part] := x;
return;
end if;
else
[part] := p;
Push(x, n, p, part);
Push(x-p, n-1, p, @next part);
end if;
end loop;
r := 0;
end sub;
sub showpartition(x: uint32, n: uint8) is
print("Partitioning ");
print_i32(x);
print(" with ");
print_i8(n);
print(" primes: ");
var part: uint32[64];
if partition(x, n, &part[0]) != 0 then
print_i32(part[0]);
var i: @indexof part := 1;
while i < n as @indexof part loop
print_char('+');
print_i32(part[i]);
i := i + 1;
end loop;
else
print("Not possible");
end if;
print_nl();
end sub;
sieve();
record Test is
x: uint32;
n: uint8;
end record;
var tests: Test[] := {
{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
{22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}
};
var test: @indexof tests := 0;
while test < @sizeof tests loop
showpartition(tests[test].x, tests[test].n);
test := test + 1;
end loop;
- Output:
Partitioning 99809 with 1 primes: 99809 Partitioning 18 with 2 primes: 5+13 Partitioning 19 with 3 primes: 3+5+11 Partitioning 20 with 4 primes: Not possible Partitioning 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioning 22699 with 1 primes: 22699 Partitioning 22699 with 2 primes: 2+22697 Partitioning 22699 with 3 primes: 3+5+22691 Partitioning 22699 with 4 primes: 2+3+43+22651 Partitioning 40355 with 3 primes: 3+139+40213
D
import std.array : array;
import std.range : take;
import std.stdio;
bool isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
auto generatePrimes() {
struct Seq {
int p = 2;
bool empty() {
return p < 0;
}
int front() {
return p;
}
void popFront() {
if (p==2) {
p++;
} else {
p += 2;
while (!empty && !p.isPrime) {
p += 2;
}
}
}
}
return Seq();
}
bool findCombo(int k, int x, int m, int n, int[] combo) {
import std.algorithm : map, sum;
auto getPrime = function int(int idx) => primes[idx];
if (k >= m) {
if (combo.map!getPrime.sum == x) {
auto word = (m > 1) ? "primes" : "prime";
writef("Partitioned %5d with %2d %s ", x, m, word);
foreach (i; 0..m) {
write(primes[combo[i]]);
if (i < m-1) {
write('+');
} else {
writeln();
}
}
return true;
}
} else {
foreach (j; 0..n) {
if (k==0 || j>combo[k-1]) {
combo[k] = j;
bool foundCombo = findCombo(k+1, x, m, n, combo);
if (foundCombo) {
return true;
}
}
}
}
return false;
}
void partition(int x, int m) {
import std.exception : enforce;
import std.algorithm : filter;
enforce(x>=2 && m>=1 && m<x);
auto lessThan = delegate int(int a) => a<=x;
auto filteredPrimes = primes.filter!lessThan.array;
auto n = filteredPrimes.length;
enforce(n>=m, "Not enough primes");
int[] combo = new int[m];
if (!findCombo(0, x, m, n, combo)) {
auto word = (m > 1) ? "primes" : "prime";
writefln("Partitioned %5d with %2d %s: (not possible)", x, m, word);
}
}
int[] primes;
void main() {
// generate first 50,000 and call it good
primes = generatePrimes().take(50_000).array;
auto a = [
[99809, 1],
[ 18, 2],
[ 19, 3],
[ 20, 4],
[ 2017, 24],
[22699, 1],
[22699, 2],
[22699, 3],
[22699, 4],
[40355, 3]
];
foreach(p; a) {
partition(p[0], p[1]);
}
}
- Output:
Partitioned 99809 with 1 prime 99809 Partitioned 18 with 2 primes 5+13 Partitioned 19 with 3 primes 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime 22699 Partitioned 22699 with 2 primes 2+22697 Partitioned 22699 with 3 primes 3+5+22691 Partitioned 22699 with 4 primes 2+3+43+22651 Partitioned 40355 with 3 primes 3+139+40213
F#
This task uses Extensible Prime Generator (F#)
// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017
let rcTask n ng =
let rec fN i g e l = seq{
match i with
|1 -> if isPrime g then yield Some (g::e) else yield None
|_ -> yield! Seq.mapi (fun n a->fN (i-1) (g-a) (a::e) (Seq.skip (n+1) l)) (l|>Seq.takeWhile(fun n->(g-n)>n))|>Seq.concat}
match fN n ng [] primes |> Seq.tryPick id with
|Some n->printfn "%d is the sum of %A" ng n
|_ ->printfn "No Solution"
- Output:
rcTask 1 99089 -> 99089 is the sum of [99089] rcTask 2 18 -> 18 is the sum of [13; 5] rcTask 3 19 -> 19 is the sum of [11; 5; 3] rcTask 4 20 -> No Solution rcTask 24 2017 -> 2017 is the sum of [1129; 97; 79; 73; 71; 67; 61; 59; 53; 47; 43; 41; 37; 31; 29; 23; 19; 17; 13; 11; 7; 5; 3; 2] rcTask 1 2269 -> 2269 is the sum of [2269] rcTask 2 2269 -> 2269 is the sum of [2267; 2] rcTask 3 2269 -> 2269 is the sum of [2243; 23; 3] rcTask 4 2269 -> 2269 is the sum of [2251; 13; 3; 2] rcTask 3 40355 -> 40355 is the sum of [40213; 139; 3]
Factor
USING: formatting fry grouping kernel math.combinatorics
math.parser math.primes sequences ;
: partition ( x n -- str )
over [ primes-upto ] 2dip '[ sum _ = ] find-combination
[ number>string ] map "+" join ;
: print-partition ( x n seq -- )
[ "no solution" ] when-empty
"Partitioned %5d with %2d primes: %s\n" printf ;
{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699
4 40355 3 } 2 group
[ first2 2dup partition print-partition ] each
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: no solution Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Fortran
module primes_module
implicit none
integer,allocatable :: p(:)
integer :: a(0:32), b(0:32)
integer,private :: sum_primes, number
contains
!
subroutine setnum(val)
implicit none
integer :: val
number = val
return
end subroutine setnum
!
subroutine init(thesize)
implicit none
integer :: thesize
!
allocate(p(thesize))
p=0
a=0
b=0
return
end subroutine init
!
subroutine genp(high) ! Store all primes up to high in the array p
integer, intent(in) :: high
integer :: i, numprimes, j,k
logical*1 :: bk(0:high)
!
bk = .false.
p = 0
a = 0
b = 0
call eratosthenes(bk , high)
j = 0
numprimes = count(bk)
k = 0
do i = 1,high
if(bk(i))then
j = j+1
p(j) = i
if(j==numprimes)exit !No need to loop more, all primes stored
endif
end do
print*,'numprimes',numprimes, i,p(j)
return
end subroutine genp
subroutine getp(z) ! used to update the zth prime number in the sequence of primes that are being used to partition the integer number.
integer :: z
integer :: w
!
if (a(z) == 0)a(z) = a(z-1)
a(z) = a(z) + 1
b(z) = p(a(z))
return
end subroutine getp
subroutine part(num_found)
integer, intent(in) :: num_found
integer :: i, s, k, r
logical :: bu
a = 0
do i = 1, num_found
call getp(i)
end do
infinite: do
sum_primes = 0
bu = .false.
nextin:do s = 1, num_found
sum_primes = sum_primes + b(s) !Adds the sth prime to sum_primes.
if (sum_primes > number) then !If the sum of primes exceeds number:
if (s == 1)then
exit infinite !If only one prime has been added, exit the infinite loop.
endif
a(s:num_found) = 0 ! Resets the indices of the primes from s to num_found
do r = s - 1, num_found ! Gets the next set of primes from s-1 to num_found
call getp(r)
end do
bu = .true. ! Sets bu to true and exits the loop over the primes
exit nextin
end if
end do nextin
if (.not. bu) then ! If bu is false (meaning the sum of primes does not exceed number)
if (sum_primes == number) exit infinite !We got it so go
if (sum_primes < number) then
call getp(num_found) ! If the sum of primes is less than number, gets the next prime
else
error stop " Something wrong here!"
endif
endif
end do infinite
write( *,'(/,a,1x,i0,1x,a,1x,i0,1x,a)',advance='yes') "Partition", number, "into", num_found,trim(adjustl(list(num_found)))
end subroutine part
!
function list(num_found)
integer, intent(in) :: num_found
integer :: i
character(len=128) :: list
character(len = 10):: pooka
!
write(list,'(i0)') b(1)
if (sum_primes == number) then
do i = 2, num_found
pooka = ''
write(pooka,'(i0)') b(i)
list = trim(list) // " + " // adjustl(pooka)
end do
else
list = "(not possible)"
end if
list = "primes: " // list
end function list
!
subroutine eratosthenes(p , n)
implicit none
!
! dummy arguments
!
integer :: n
logical*1 , dimension(0:*) :: p
intent (in) n
intent (inout) p
!
! local variables
!
integer :: i
integer :: ii
logical :: oddeven
integer :: pr
!
p(0:n) = .false.
p(1) = .false.
p(2) = .true.
oddeven = .true.
do i = 3 , n,2
p(i) = .true.
end do
do i = 2 , int(sqrt(float(n)))
ii = i + i
if( p(i) )then
do pr = i*i , n , ii
p(pr) = .false.
end do
end if
end do
return
end subroutine eratosthenes
end module primes_module
program prime_partition
use primes_module
implicit none
integer :: x, n,i
integer :: xx,yy
integer :: values(10,2)
! The given dataset from Rosetta Code
! partition 99809 with 1 prime.
! partition 18 with 2 primes.
! partition 19 with 3 primes.
! partition 20 with 4 primes.
! partition 2017 with 24 primes.
! partition 22699 with 1, 2, 3, and 4 primes.
! partition 40355 with 3 primes.
values(1,:) = (/99809,1/)
values(2,:) = (/18,2/)
values(3,:) = (/19,3/)
values(4,:) = (/20,4/)
values(5,:) = (/2017,24/)
values(6,:) = (/22699, 1/)
values(7,:) = (/22699, 2/)
values(8,:) = (/22699, 3/)
values(9,:) = (/22699, 4/)
values(10,:) = (/40355, 3/)
i = maxval(values(1:10,1))*2
call init(i) ! Set up a few basics
call genp(i) ! Generate primes up to i
do i = 1,10
call setnum( values(i,1))
call part(values(i,2))
end do
Stop 'Successfully completed'
end program prime_partition
- Output:
Partition 99809 into 1 primes: 99809 Partition 18 into 2 primes : 5 + 13 Partition 19 into 3 primes : 3 + 5 + 11 Partition 20 into 4 primes : (not possible) Partition 2017 into 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partition 22699 into 1 primes: 22699 Partition 22699 into 2 primes: 2 + 22697 Partition 22699 into 3 primes: 3 + 5 + 22691 Partition 22699 into 4 primes: 2 + 3 + 43 + 22651 Partition 40355 into 3 primes: 3 + 139 + 40213
Go
... though uses a sieve to generate the relevant primes.
package main
import (
"fmt"
"log"
)
var (
primes = sieve(100000)
foundCombo = false
)
func sieve(limit uint) []uint {
primes := []uint{2}
c := make([]bool, limit+1) // composite = true
// no need to process even numbers > 2
p := uint(3)
for {
p2 := p * p
if p2 > limit {
break
}
for i := p2; i <= limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
for i := uint(3); i <= limit; i += 2 {
if !c[i] {
primes = append(primes, i)
}
}
return primes
}
func findCombo(k, x, m, n uint, combo []uint) {
if k >= m {
sum := uint(0)
for _, c := range combo {
sum += primes[c]
}
if sum == x {
s := "s"
if m == 1 {
s = " "
}
fmt.Printf("Partitioned %5d with %2d prime%s: ", x, m, s)
for i := uint(0); i < m; i++ {
fmt.Print(primes[combo[i]])
if i < m-1 {
fmt.Print("+")
} else {
fmt.Println()
}
}
foundCombo = true
}
} else {
for j := uint(0); j < n; j++ {
if k == 0 || j > combo[k-1] {
combo[k] = j
if !foundCombo {
findCombo(k+1, x, m, n, combo)
}
}
}
}
}
func partition(x, m uint) error {
if !(x >= 2 && m >= 1 && m < x) {
return fmt.Errorf("x must be at least 2 and m in [1, x)")
}
n := uint(0)
for _, prime := range primes {
if prime <= x {
n++
}
}
if n < m {
return fmt.Errorf("not enough primes")
}
combo := make([]uint, m)
foundCombo = false
findCombo(0, x, m, n, combo)
if !foundCombo {
s := "s"
if m == 1 {
s = " "
}
fmt.Printf("Partitioned %5d with %2d prime%s: (impossible)\n", x, m, s)
}
return nil
}
func main() {
a := [...][2]uint{
{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
{22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3},
}
for _, p := range a {
err := partition(p[0], p[1])
if err != nil {
log.Println(err)
}
}
}
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (impossible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Haskell
import Data.List (delete, intercalate)
import Data.Numbers.Primes (primes)
import Data.Bool (bool)
-------------------- PRIME PARTITIONS ---------------------
partitions :: Int -> Int -> [Int]
partitions x n
| n <= 1 =
[ x
| x == last ps ]
| otherwise = go ps x n
where
ps = takeWhile (<= x) primes
go ps_ x 1 =
[ x
| x `elem` ps_ ]
go ps_ x n = ((flip bool [] . head) <*> null) (ps_ >>= found)
where
found p =
((flip bool [] . return . (p :)) <*> null)
((go =<< delete p . flip takeWhile ps_ . (>=)) (x - p) (pred n))
-------------------------- TEST ---------------------------
main :: IO ()
main =
mapM_ putStrLn $
(\(x, n) ->
intercalate
" -> "
[ justifyLeft 9 ' ' (show (x, n))
, let xs = partitions x n
in bool
(tail $ concatMap (('+' :) . show) xs)
"(no solution)"
(null xs)
]) <$>
concat
[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]
, (,) 22699 <$> [1 .. 4]
, [(40355, 3)]
]
------------------------- GENERIC -------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)
- Output:
(99809,1) -> 99809 (18,2) -> 5+13 (19,3) -> 3+5+11 (20,4) -> (no solution) (2017,24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 (22699,1) -> 22699 (22699,2) -> 2+22697 (22699,3) -> 3+5+22691 (22699,4) -> 2+3+43+22651 (40355,3) -> 3+139+40213
J
load 'format/printf'
NB. I don't know of any way to easily make an idiomatic lazy exploration,
NB. except falling back on explicit imperative control strutures.
NB. However this is clearly not where J shines neither with speed nor elegance.
primes_up_to =: monad def 'p: i. _1 p: 1 + y'
terms_as_text =: monad def '; }: , (": each y),.<'' + '''
search_next_terms =: dyad define
acc=. x NB. -> an accumulator that contains given beginning of the partition.
p=. >0{y NB. -> number of elements wanted in the partition
ns=. >1{y NB. -> candidate values to be included in the partition
sum=. >2{y NB. -> the integer to partition
if. p=0 do.
if. sum=+/acc do. acc return. end.
else.
for_m. i. (#ns)-(p-1) do.
r =. (acc,m{ns) search_next_terms (p-1);((m+1)}.ns);sum
if. #r do. r return. end.
end.
end.
0$0 NB. Empty result if nothing found at the end of this path.
)
NB. Prints a partition of y primes whose sum equals x.
partitioned_in =: dyad define
terms =. (0$0) search_next_terms y;(primes_up_to x);x
if. #terms do.
'As the sum of %d primes, %d = %s' printf y;x; terms_as_text terms
else.
'Didn''t find a way to express %d as a sum of %d different primes.' printf x;y
end.
)
tests=: (99809 1) ; (18 2) ; (19 3) ; (20 4) ; (2017 24) ; (22699 1) ; (22699 2) ; (22699 3) ; (22699 4)
(0&{ partitioned_in 1&{) each tests
- Output:
As the sum of 1 primes, 99809 = 99809 As the sum of 2 primes, 18 = 5 + 13 As the sum of 3 primes, 19 = 3 + 5 + 11 Didn't find a way to express 20 as a sum of 4 different primes. As the sum of 24 primes, 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 As the sum of 1 primes, 22699 = 22699 As the sum of 2 primes, 22699 = 2 + 22697 As the sum of 3 primes, 22699 = 3 + 5 + 22691 As the sum of 4 primes, 22699 = 2 + 3 + 43 + 22651 As the sum of 3 primes, 40355 = 3 + 139 + 40213
Java
import java.util.Arrays;
import java.util.stream.IntStream;
public class PartitionInteger {
private static final int[] primes = IntStream.concat(IntStream.of(2), IntStream.iterate(3, n -> n + 2))
.filter(PartitionInteger::isPrime)
.limit(50_000)
.toArray();
private static boolean isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
private static boolean findCombo(int k, int x, int m, int n, int[] combo) {
boolean foundCombo = false;
if (k >= m) {
if (Arrays.stream(combo).map(i -> primes[i]).sum() == x) {
String s = m > 1 ? "s" : "";
System.out.printf("Partitioned %5d with %2d prime%s: ", x, m, s);
for (int i = 0; i < m; ++i) {
System.out.print(primes[combo[i]]);
if (i < m - 1) System.out.print('+');
else System.out.println();
}
foundCombo = true;
}
} else {
for (int j = 0; j < n; ++j) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j;
if (!foundCombo) {
foundCombo = findCombo(k + 1, x, m, n, combo);
}
}
}
}
return foundCombo;
}
private static void partition(int x, int m) {
if (x < 2 || m < 1 || m >= x) {
throw new IllegalArgumentException();
}
int[] filteredPrimes = Arrays.stream(primes).filter(it -> it <= x).toArray();
int n = filteredPrimes.length;
if (n < m) throw new IllegalArgumentException("Not enough primes");
int[] combo = new int[m];
boolean foundCombo = findCombo(0, x, m, n, combo);
if (!foundCombo) {
String s = m > 1 ? "s" : " ";
System.out.printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, s);
}
}
public static void main(String[] args) {
partition(99809, 1);
partition(18, 2);
partition(19, 3);
partition(20, 4);
partition(2017, 24);
partition(22699, 1);
partition(22699, 2);
partition(22699, 3);
partition(22699, 4);
partition(40355, 3);
}
}
- Output:
Partitioned 99809 with 1 prime: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
jq
Works with jq and with gojq, the Go implementation of jq
Prime-number functions
# Is the input integer a prime?
def is_prime:
if . == 2 then true
else 2 < . and . % 2 == 1 and
. as $in
| (($in + 1) | sqrt) as $m
| (((($m - 1) / 2) | floor) + 1) as $max
| all( range(1; $max) ; $in % ((2 * .) + 1) > 0 )
end;
# Is the input integer a prime?
# `previous` should be a sorted array of consecutive primes
# greater than 1 and at least including the greatest prime less than (.|sqrt)
def is_prime(previous):
. as $in
| (($in + 1) | sqrt) as $sqrt
| first(previous[]
| if . > $sqrt then 1
elif 0 == ($in % .) then 0
else empty
end) // 1
| . == 1;
# This assumes . is an array of consecutive primes beginning with [2,3]
def next_prime:
. as $previous
| (2 + .[-1] )
| until(is_prime($previous); . + 2) ;
# Emit primes from 2 up
def primes:
# The helper function has arity 0 for TCO
# It expects its input to be an array of previously found primes, in order:
def next:
. as $previous
| ($previous|next_prime) as $next
| $next, (($previous + [$next]) | next) ;
2, 3, ([2,3] | next);
# The primes less than or equal to $x
def primes($x):
label $out
| primes | if . > $x then break $out else . end;
Helper function
# Emit a stream consisting of arrays, a, of $n items from the input array,
# preserving order, subject to (a|add) == $sum
def take($n; $sum):
def take:
. as [$m, $in, $s]
| if $m==0 and $s == 0 then []
elif $m==0 or $s <= 0 then empty
else range(0;$in|length) as $i
| $in[$i] as $x
| if $x > $s then empty
else [$x] + ([$m-1, $in[$i+1:], $s - $x] | take)
end
end;
[$n, ., $sum] | take;
Partitioning an integer into $n primes
# This function emits a possibly empty stream of arrays.
# Assuming $primes is primes(.), each array corresponds to a
# partition of the input into $n distinct primes.
# The algorithm is unoptimized.
# The output is a stream of arrays, which would be empty
def primepartition($n; $primes):
. as $x
| if $n == 1
then if $primes[-1] == $x then [$x] else null end
else (if $primes[-1] == $x then $primes[:-1] else $primes end) as $primes
| ($primes | take($n; $x))
end ;
# See primepartition/2
def primepartition($n):
. as $x
| if $n == 1
then if is_prime then [.] else null end
else primepartition($n; [primes($x)])
end;
# Compute first(primepartition($n)) for each $n in the array $ary
def primepartitions($ary):
. as $x
| [primes($x)] as $px
| $ary[] as $n
| $x
| first(primepartition($n; $px));
def task($x; $n):
def pp:
if . then join("+") else "(not possible)" end;
if $n|type == "array" then task($x; $n[])
else "A partition of \($x) into \($n) parts: \(first($x | primepartition($n)) | pp )"
end;
The tasks
task(18; 2),
task(19; 3),
task(20; 4),
task(2017; 24),
task(22699; [1,2,3,4]),
task(40355; 3)
- Output:
A partition of 18 into 2 parts: 5+13 A partition of 19 into 3 parts: 3+5+11 A partition of 2017 into 24 parts: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 A partition of 22699 into 1 parts: 22699 A partition of 22699 into 2 parts: 2+22697 A partition of 22699 into 3 parts: 3+5+22691 A partition of 22699 into 4 parts: 2+3+43+22651 A partition of 40355 into 3 parts: 3+139+40213
Julia
using Primes, Combinatorics
function primepartition(x::Int64, n::Int64)
if n == oftype(n, 1)
return isprime(x) ? [x] : Int64[]
else
for combo in combinations(primes(x), n)
if sum(combo) == x
return combo
end
end
end
return Int64[]
end
for (x, n) in [[ 18, 2], [ 19, 3], [ 20, 4], [99807, 1], [99809, 1],
[ 2017, 24],[22699, 1], [22699, 2], [22699, 3], [22699, 4] ,[40355, 3]]
ans = primepartition(x, n)
println("Partition of ", x, " into ", n, " primes: ",
isempty(ans) ? "impossible" : join(ans, " + "))
end
- Output:
Partition of 18 into 2 prime pieces: 5 + 13 Partition of 19 into 3 prime pieces: 3 + 5 + 11 Partition of 20 into 4 prime pieces: impossible Partition of 99807 into 1 prime piece: impossible Partition of 99809 into 1 prime piece: 99809 Partition of 2017 into 24 prime pieces: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partition of 22699 into 1 prime piece: 22699 Partition of 22699 into 2 prime pieces: 2 + 22697 Partition of 22699 into 3 prime pieces: 3 + 5 + 22691 Partition of 22699 into 4 prime pieces: 2 + 3 + 43 + 22651 Partition of 40355 into 3 prime pieces: 3 + 139 + 40213
Kotlin
// version 1.1.2
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning
import kotlin.coroutines.experimental.*
val primes = generatePrimes().take(50_000).toList() // generate first 50,000 say
var foundCombo = false
fun isPrime(n: Int) : Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
var d : Int = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
fun generatePrimes() =
buildSequence {
yield(2)
var p = 3
while (p <= Int.MAX_VALUE) {
if (isPrime(p)) yield(p)
p += 2
}
}
fun findCombo(k: Int, x: Int, m: Int, n: Int, combo: IntArray) {
if (k >= m) {
if (combo.sumBy { primes[it] } == x) {
val s = if (m > 1) "s" else " "
print("Partitioned ${"%5d".format(x)} with ${"%2d".format(m)} prime$s: ")
for (i in 0 until m) {
print(primes[combo[i]])
if (i < m - 1) print("+") else println()
}
foundCombo = true
}
}
else {
for (j in 0 until n) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j
if (!foundCombo) findCombo(k + 1, x, m, n, combo)
}
}
}
}
fun partition(x: Int, m: Int) {
require(x >= 2 && m >= 1 && m < x)
val filteredPrimes = primes.filter { it <= x }
val n = filteredPrimes.size
if (n < m) throw IllegalArgumentException("Not enough primes")
val combo = IntArray(m)
foundCombo = false
findCombo(0, x, m, n, combo)
if (!foundCombo) {
val s = if (m > 1) "s" else " "
println("Partitioned ${"%5d".format(x)} with ${"%2d".format(m)} prime$s: (not possible)")
}
}
fun main(args: Array<String>) {
val a = arrayOf(
99809 to 1,
18 to 2,
19 to 3,
20 to 4,
2017 to 24,
22699 to 1,
22699 to 2,
22699 to 3,
22699 to 4,
40355 to 3
)
for (p in a) partition(p.first, p.second)
}
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Lingo
Using the prime generator class "sieve" from task Extensible prime generator#Lingo.
----------------------------------------
-- returns a sorted list of the <cnt> smallest unique primes that add up to <n>,
-- or FALSE if there is no such partition of primes for <n>
----------------------------------------
on getPrimePartition (n, cnt, primes, ptr, res)
if voidP(primes) then
primes = _global.sieve.getPrimesInRange(2, n)
ptr = 1
res = []
end if
if cnt=1 then
if primes.getPos(n)>=ptr then
res.addAt(1, n)
if res.count=cnt+ptr-1 then
return res
end if
return TRUE
end if
else
repeat with i = ptr to primes.count
p = primes[i]
ok = getPrimePartition(n-p, cnt-1, primes, i+1, res)
if ok then
res.addAt(1, p)
if res.count=cnt+ptr-1 then
return res
end if
return TRUE
end if
end repeat
end if
return FALSE
end
----------------------------------------
-- gets partition, prints formatted result
----------------------------------------
on showPrimePartition (n, cnt)
res = getPrimePartition(n, cnt)
if res=FALSE then res = "not prossible"
else res = implode("+", res)
put "Partitioned "&n&" with "&cnt&" primes: " & res
end
----------------------------------------
-- implodes list into string
----------------------------------------
on implode (delim, tList)
str = ""
repeat with i=1 to tList.count
put tList[i]&delim after str
end repeat
delete char (str.length+1-delim.length) to str.length of str
return str
end
-- main
_global.sieve = script("sieve").new()
showPrimePartition(99809, 1)
showPrimePartition(18, 2)
showPrimePartition(19, 3)
showPrimePartition(20, 4)
showPrimePartition(2017, 24)
showPrimePartition(22699, 1)
showPrimePartition(22699, 2)
showPrimePartition(22699, 3)
showPrimePartition(22699, 4)
showPrimePartition(40355, 3)
- Output:
-- "Partitioned 99809 with 1 primes: 99809" -- "Partitioned 18 with 2 primes: 5+13" -- "Partitioned 19 with 3 primes: 3+5+11" -- "Partitioned 20 with 4 primes: not prossible" -- "Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129" -- "Partitioned 22699 with 1 primes: 22699" -- "Partitioned 22699 with 2 primes: 2+22697" -- "Partitioned 22699 with 3 primes: 3+5+22691" -- "Partitioned 22699 with 4 primes: 2+3+43+22651" -- "Partitioned 40355 with 3 primes: 3+139+40213"
Mathematica/Wolfram Language
NextPrimeMemo[n_] := (NextPrimeMemo[n] = NextPrime[n]);(*This improves performance by 30% or so*)
PrimeList[count_] := Prime/@Range[count];(*Just a helper to create an initial list of primes of the desired length*)
AppendPrime[list_] := Append[list,NextPrimeMemo[Last@list]];(*Another helper that makes creating the next candidate less verbose*)
NextCandidate[{list_, target_}] :=
With[
{len = Length@list, nextHead = NestWhile[Drop[#, -1] &, list, Total[#] > target &]},
Which[
{} == nextHead, {{}, target},
Total[nextHead] == target && Length@nextHead == len, {nextHead, target},
True, {NestWhile[AppendPrime, MapAt[NextPrimeMemo, nextHead, -1], Length[#] < Length[list] &], target}
]
];(*This is the meat of the matter. If it determines that the job is impossible, it returns a structure with an empty list of summands. If the input satisfies the success criteria, it just returns it (this will be our fixed point). Otherwise, it generates a subsequent candidate.*)
FormatResult[{list_, number_}, targetCount_] :=
StringForm[
"Partitioned `1` with `2` prime`4`: `3`",
number,
targetCount,
If[0 == Length@list, "no solutions found", StringRiffle[list, "+"]],
If[1 == Length@list, "", "s"]]; (*Just a helper for pretty-printing the output*)
PrimePartition[number_, count_] := FixedPoint[NextCandidate, {PrimeList[count], number}];(*This is where things kick off. NextCandidate will eventually return the failure format or a success, and either of those are fixed points of the function.*)
TestCases =
{
{99809, 1},
{18, 2},
{19, 3},
{20, 4},
{2017, 24},
{22699, 1},
{22699, 2},
{22699, 3},
{22699, 4},
{40355, 3}
};
TimedResults = ReleaseHold[Hold[AbsoluteTiming[FormatResult[PrimePartition @@ #, Last@#]]] & /@TestCases](*I thought it would be interesting to include the timings, which are in seconds*)
TimedResults // TableForm
- Output:
0.111699 Partitioned 99809 with 1 prime: 99809 0.000407 Partitioned 18 with 2 primes: 5+13 0.000346 Partitioned 19 with 3 primes: 3+5+11 0.000765 Partitioned 20 with 4 primes: no solutions found 0.008381 Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 0.028422 Partitioned 22699 with 1 prime: 22699 0.02713 Partitioned 22699 with 2 primes: 2+22697 20.207 Partitioned 22699 with 3 primes: 3+5+22691 0.357536 Partitioned 22699 with 4 primes: 2+3+43+22651 57.9928 Partitioned 40355 with 3 primes: 3+139+40213
Nim
import math, sugar
const N = 100_000
# Fill a sieve of Erathostenes.
var isPrime {.noInit.}: array[2..N, bool]
for item in isPrime.mitems: item = true
for n in 2..int(sqrt(N.toFloat)):
if isPrime[n]:
for k in countup(n * n, N, n):
isPrime[k] = false
# Build list of primes.
let primes = collect(newSeq):
for n in 2..N:
if isPrime[n]: n
proc partition(n, k: int; start = 0): seq[int] =
## Partition "n" in "k" primes starting at position "start" in "primes".
## Return the list of primes or an empty list if partitionning is impossible.
if k == 1:
return if isPrime[n] and n >= primes[start]: @[n] else: @[]
for i in start..primes.high:
let a = primes[i]
if n - a <= 1: break
result = partition(n - a, k - 1, i + 1)
if result.len != 0:
return a & result
when isMainModule:
import strutils
func plural(k: int): string =
if k <= 1: "" else: "s"
for (n, k) in [(99809, 1), (18, 2), (19, 3), (20, 4),
(2017, 24), (22699, 1), (22699, 2),
(22699, 3), (22699, 4), (40355, 3)]:
let part = partition(n, k)
if part.len == 0:
echo n, " cannot be partitionned into ", k, " prime", plural(k)
else:
echo n, " = ", part.join(" + ")
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitionned into 4 primes 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
PARI/GP
partDistinctPrimes(x,n,mn=2)=
{
if(n==1, return(if(isprime(x) && mn<=x, [x], 0)));
if((x-n)%2,
if(mn>2, return(0));
my(t=partDistinctPrimes(x-2,n-1,3));
return(if(t, concat(2,t), 0))
);
if(n==2,
forprime(p=mn,(x-1)\2,
if(isprime(x-p), return([p,x-p]))
);
return(0)
);
if(n<1, return(if(n, 0, [])));
\\ x is the sum of 3 or more odd primes
my(t);
forprime(p=mn,(x-1)\n,
t=partDistinctPrimes(x-p,n-1,p+2);
if(t, return(concat(p,t)))
);
0;
}
displayNicely(x,n)=
{
printf("Partitioned%6d with%3d prime", x, n);
if(n!=1, print1("s"));
my(t=partDistinctPrimes(x,n));
if(t===0, print(": (not possible)"); return);
if(#t, print1(": "t[1]));
for(i=2,#t, print1("+"t[i]));
print();
}
V=[[99809,1], [18,2], [19,3], [20,4], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
for(i=1,#V, call(displayNicely, V[i]))
- Output:
Partitioned 99809 with 1 prime: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Perl
It is tempting to use the partition iterator which takes a "isprime" flag, but this task calls for unique values. Hence the combination iterator over an array of primes makes more sense.
use ntheory ":all";
sub prime_partition {
my($num, $parts) = @_;
return is_prime($num) ? [$num] : undef if $parts == 1;
my @p = @{primes($num)};
my $r;
forcomb { lastfor, $r = [@p[@_]] if vecsum(@p[@_]) == $num; } @p, $parts;
$r;
}
foreach my $test ([18,2], [19,3], [20,4], [99807,1], [99809,1], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]) {
my $partar = prime_partition(@$test);
printf "Partition %5d into %2d prime piece%s %s\n", $test->[0], $test->[1], ($test->[1] == 1) ? ": " : "s:", defined($partar) ? join("+",@$partar) : "not possible";
}
- Output:
Partition 18 into 2 prime pieces: 5+13 Partition 19 into 3 prime pieces: 3+5+11 Partition 20 into 4 prime pieces: not possible Partition 99807 into 1 prime piece: not possible Partition 99809 into 1 prime piece: 99809 Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 into 1 prime piece: 22699 Partition 22699 into 2 prime pieces: 2+22697 Partition 22699 into 3 prime pieces: 3+5+22691 Partition 22699 into 4 prime pieces: 2+3+43+22651 Partition 40355 into 3 prime pieces: 3+139+40213
Phix
with javascript_semantics requires("1.0.2") -- (join(fmt)) function partition(integer v, n, idx=0) if n=1 then return iff(is_prime(v)?{v}:0) end if while true do idx += 1 integer np = get_prime(idx) if np>=floor(v/2) then exit end if object res = partition(v-np, n-1, idx) if sequence(res) then res = prepend(res,np) return res end if end while return 0 end function constant tests = {{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24}, {22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}} for i=1 to length(tests) do integer {v,n} = tests[i] object res = partition(v,n) res = iff(res=0?"not possible":join(res," + ",fmt:="%d")) printf(1,"Partition %d into %d primes: %s\n",{v,n,res}) end for
- Output:
Partition 99809 into 1 primes: 99809 Partition 18 into 2 primes: 5 + 13 Partition 19 into 3 primes: 3 + 5 + 11 Partition 20 into 4 primes: not possible Partition 2017 into 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partition 22699 into 1 primes: 22699 Partition 22699 into 2 primes: 2 + 22697 Partition 22699 into 3 primes: 3 + 5 + 22691 Partition 22699 into 4 primes: 2 + 3 + 43 + 22651 Partition 40355 into 3 primes: 3 + 139 + 40213
Prolog
prime_partition(N, 1, [N], Min):-
is_prime(N),
N > Min,
!.
prime_partition(N, K, [P|Rest], Min):-
K > 1,
is_prime(P),
P > Min,
P < N,
K1 is K - 1,
N1 is N - P,
prime_partition(N1, K1, Rest, P),
!.
prime_partition(N, K, Primes):-
prime_partition(N, K, Primes, 1).
print_primes([Prime]):-
!,
writef('%w\n', [Prime]).
print_primes([Prime|Primes]):-
writef('%w + ', [Prime]),
print_primes(Primes).
print_prime_partition(N, K):-
prime_partition(N, K, Primes),
!,
writef('%w = ', [N]),
print_primes(Primes).
print_prime_partition(N, K):-
writef('%w cannot be partitioned into %w primes.\n', [N, K]).
main:-
find_prime_numbers(100000),
print_prime_partition(99809, 1),
print_prime_partition(18, 2),
print_prime_partition(19, 3),
print_prime_partition(20, 4),
print_prime_partition(2017, 24),
print_prime_partition(22699, 1),
print_prime_partition(22699, 2),
print_prime_partition(22699, 3),
print_prime_partition(22699, 4),
print_prime_partition(40355, 3).
Module for finding prime numbers up to some limit:
:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.
find_prime_numbers(N):-
retractall(is_prime(_)),
assertz(is_prime(2)),
init_sieve(N, 3),
sieve(N, 3).
init_sieve(N, P):-
P > N,
!.
init_sieve(N, P):-
assertz(is_prime(P)),
Q is P + 2,
init_sieve(N, Q).
sieve(N, P):-
P * P > N,
!.
sieve(N, P):-
is_prime(P),
!,
S is P * P,
cross_out(S, N, P),
Q is P + 2,
sieve(N, Q).
sieve(N, P):-
Q is P + 2,
sieve(N, Q).
cross_out(S, N, _):-
S > N,
!.
cross_out(S, N, P):-
retract(is_prime(S)),
!,
Q is S + 2 * P,
cross_out(Q, N, P).
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
Python
from itertools import combinations as cmb
def isP(n):
if n == 2:
return True
if n % 2 == 0:
return False
return all(n % x > 0 for x in range(3, int(n ** 0.5) + 1, 2))
def genP(n):
p = [2]
p.extend([x for x in range(3, n + 1, 2) if isP(x)])
return p
data = [
(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
(22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)]
for n, cnt in data:
ci = iter(cmb(genP(n), cnt))
while True:
try:
c = next(ci)
if sum(c) == n:
print(' '.join(
[repr((n, cnt)), "->", '+'.join(str(s) for s in c)]
))
break
except StopIteration:
print(repr((n, cnt)) + " -> Not possible")
break
- Output:
(99809, 1) -> 99809 (18, 2) -> 5+13 (19, 3) -> 3+5+11 (20, 4) -> Not possible (2017, 24) -> 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 (22699, 1) -> 22699 (22699, 2) -> 2+22697 (22699, 3) -> 3+5+22691 (22699, 4) -> 2+3+43+22651 (40355, 3) -> 3+139+40213
Racket
#lang racket
(require math/number-theory)
(define memoised-next-prime
(let ((m# (make-hash)))
(λ (P) (hash-ref! m# P (λ () (next-prime P))))))
(define (partition-X-into-N-primes X N)
(define (partition-x-into-n-primes-starting-at-P x n P result)
(cond ((= n x 0) result)
((or (= n 0) (= x 0) (> P x)) #f)
(else
(let ((P′ (memoised-next-prime P)))
(or (partition-x-into-n-primes-starting-at-P (- x P) (- n 1) P′ (cons P result))
(partition-x-into-n-primes-starting-at-P x n P′ result))))))
(reverse (or (partition-x-into-n-primes-starting-at-P X N 2 null) (list 'no-solution))))
(define (report-partition X N)
(let ((result (partition-X-into-N-primes X N)))
(printf "partition ~a\twith ~a\tprimes: ~a~%" X N (string-join (map ~a result) " + "))))
(module+ test
(report-partition 99809 1)
(report-partition 18 2)
(report-partition 19 3)
(report-partition 20 4)
(report-partition 2017 24)
(report-partition 22699 1)
(report-partition 22699 2)
(report-partition 22699 3)
(report-partition 22699 4)
(report-partition 40355 3))
- Output:
partition 99809 with 1 primes: 99809 partition 18 with 2 primes: 5 + 13 partition 19 with 3 primes: 3 + 5 + 11 partition 20 with 4 primes: no-solution partition 2017 with 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 partition 22699 with 1 primes: 22699 partition 22699 with 2 primes: 2 + 22697 partition 22699 with 3 primes: 3 + 5 + 22691 partition 22699 with 4 primes: 2 + 3 + 43 + 22651 partition 40355 with 3 primes: 3 + 139 + 40213
Raku
(formerly Perl 6)
use Math::Primesieve;
my $sieve = Math::Primesieve.new;
# short circuit for '1' partition
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! () }
multi partition ( Int $number, Int $parts where * > 0 = 2 ) {
my @these = $sieve.primes($number);
for @these.combinations($parts) { .return if .sum == $number };
()
}
# TESTING
(18,2, 19,3, 20,4, 99807,1, 99809,1, 2017,24, 22699,1, 22699,2, 22699,3, 22699,4, 40355,3)\
.race(:1batch).map: -> $number, $parts {
say (sprintf "Partition %5d into %2d prime piece", $number, $parts),
$parts == 1 ?? ': ' !! 's: ', join '+', partition($number, $parts) || 'not possible'
}
- Output:
Partition 18 into 2 prime pieces: 5+13 Partition 19 into 3 prime pieces: 3+5+11 Partition 20 into 4 prime pieces: not possible Partition 99807 into 1 prime piece: not possible Partition 99809 into 1 prime piece: 99809 Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 into 1 prime piece: 22699 Partition 22699 into 2 prime pieces: 2+22697 Partition 22699 into 3 prime pieces: 3+5+22691 Partition 22699 into 4 prime pieces: 2+3+43+22651 Partition 40355 into 3 prime pieces: 3+139+40213
Refal
$ENTRY Go {
= <Each Test <Tests>>;
};
Tests {
= (99809 1) (18 2) (19 3) (20 4) (2017 24)
(22699 1) (22699 2) (22699 3) (22699 4) (40355 3);
};
Test {
(s.X s.N) =
<Prout 'Partitioned ' <Symb s.X> ' with ' <Symb s.N> ' primes: '
<Format <PrimePartition s.X s.N>>>;
};
Format {
F = 'not possible';
T s.N = <Symb s.N>;
T s.N e.X = <Symb s.N> '+' <Format T e.X>;
};
PrimePartition {
s.X s.N = <Partition s.X s.N <Primes s.X>>;
};
Partition {
s.X 1 e.Nums, e.Nums: {
e.1 s.X e.2 = T s.X;
e.1 = F;
};
s.X s.N = F;
s.X s.N s.Num e.Nums, <Compare s.X s.Num>: '-' =
<Partition s.X s.N e.Nums>;
s.X s.N s.Num e.Nums,
<Partition <- s.X s.Num> <- s.N 1> e.Nums>: {
T e.List = T s.Num e.List;
F = <Partition s.X s.N e.Nums>;
};
};
Primes {
s.N = <Sieve <Iota 2 s.N>>;
};
Iota {
s.End s.End = s.End;
s.Start s.End = s.Start <Iota <+ 1 s.Start> s.End>;
};
Cross {
s.Step e.List = <Cross (s.Step 1) s.Step e.List>;
(s.Step s.Skip) = ;
(s.Step 1) s.Item e.List = X <Cross (s.Step s.Step) e.List>;
(s.Step s.N) s.Item e.List = s.Item <Cross (s.Step <- s.N 1>) e.List>;
};
Sieve {
= ;
X e.List = <Sieve e.List>;
s.N e.List = s.N <Sieve <Cross s.N e.List>>;
};
Each {
s.F = ;
s.F t.X e.R = <Mu s.F t.X> <Each s.F e.R>;
};
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
REXX
Usage note: entering ranges of X and N numbers (arguments) from the command line:
- X-Y N-M ∙∙∙
which means: partition all integers (inclusive) from X ──► Y with N ──► M primes.
The to number (Y or M) can be omitted.
/*REXX program partitions integer(s) (greater than unity) into N primes. */
parse arg what /*obtain an optional list from the C.L.*/
do until what=='' /*possibly process a series of integers*/
parse var what x n what; parse var x x '-' y /*get possible range and # partitions.*/
parse var n n '-' m /* " " " " " " */
if x=='' | x=="," then x= 19 /*Not specified? Then use the default.*/
if y=='' | y=="," then y= x /* " " " " " " */
if n=='' | n=="," then n= 3 /* " " " " " " */
if m=='' | m=="," then m= n /* " " " " " " */
call genP y /*generate Y number of primes. */
do g=x to y /*partition X ───► Y into partitions.*/
do q=n to m; call part /* " G into Q primes. */
end /*q*/
end /*g*/
end /*until*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: arg high; @.1= 2; @.2= 3; #= 2 /*get highest prime, assign some vars. */
do j=@.#+2 by 2 until @.#>high /*only find odd primes from here on. */
do k=2 while k*k<=j /*divide by some known low odd primes. */
if j // @.k==0 then iterate j /*Is J divisible by P? Then ¬ prime.*/
end /*k*/ /* [↓] a prime (J) has been found. */
#= # + 1; @.#= j /*bump prime count; assign prime to @.*/
end /*j*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
getP: procedure expose i. p. @.; parse arg z /*bump the prime in the partition list.*/
if i.z==0 then do; _= z - 1; i.z= i._; end
i.z= i.z + 1; _= i.z; p.z= @._; return 0
/*──────────────────────────────────────────────────────────────────────────────────────*/
list: _= p.1; if $==g then do j=2 to q; _= _ p.j
end /*j*/
else _= '__(not_possible)'
return 'prime' || word("s", 1 + (q==1)) translate(_, '+ ', " _") /*plural? */
/*──────────────────────────────────────────────────────────────────────────────────────*/
part: i.= 0; do j=1 for q; call getP j
end /*j*/
do !=0 by 0; $= 0 /*!: a DO variable for LEAVE & ITERATE*/
do s=1 for q; $= $ + p.s /* [↓] is sum of the primes too large?*/
if $>g then do; if s==1 then leave ! /*perform a quick exit?*/
do k=s to q; i.k= 0; end /*k*/
do r=s-1 to q; call getP r; end /*r*/
iterate !
end
end /*s*/
if $==g then leave /*is sum of the primes exactly right ? */
if $ <g then do; call getP q; iterate; end
end /*!*/ /* [↑] Is sum too low? Bump a prime.*/
say 'partitioned' center(g,9) "into" center(q, 5) list()
return
- output when using the input of: 99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355
partitioned 99809 into 1 prime: 99809 partitioned 18 into 2 primes: 5+13 partitioned 19 into 3 primes: 3+5+11 partitioned 20 into 4 primes: (not possible) partitioned 2017 into 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 partitioned 22699 into 1 prime: 22699 partitioned 22699 into 2 primes: 2+22697 partitioned 22699 into 3 primes: 3+5+22691 partitioned 22699 into 4 primes: 2+3+43+22651 partitioned 40355 into 3 primes: 3+139+40213
Ring
# Project : Partition an integer X into N primes
load "stdlib.ring"
nr = 0
num = 0
list = list(100000)
items = newlist(pow(2,len(list))-1,100000)
while true
nr = nr + 1
if isprime(nr)
num = num + 1
list[num] = nr
ok
if num = 100000
exit
ok
end
powerset(list,100000)
showarray(items,100000)
see nl
func showarray(items,ind)
for p = 1 to 20
if (p > 17 and p < 21) or p = 99809 or p = 2017 or p = 22699 or p = 40355
for n = 1 to len(items)
flag = 0
for m = 1 to ind
if items[n][m] = 0
exit
ok
flag = flag + items[n][m]
next
if flag = p
str = ""
for x = 1 to len(items[n])
if items[n][x] != 0
str = str + items[n][x] + " "
ok
next
str = left(str, len(str) - 1)
str = str + "]"
if substr(str, " ") > 0
see "" + p + " = ["
see str + nl
exit
else
str = ""
ok
ok
next
ok
next
func powerset(list,ind)
num = 0
num2 = 0
items = newlist(pow(2,len(list))-1,ind)
for i = 2 to (2 << len(list)) - 1 step 2
num2 = 0
num = num + 1
for j = 1 to len(list)
if i & (1 << j)
num2 = num2 + 1
if list[j] != 0
items[num][num2] = list[j]
ok
ok
next
next
return items
Output:
99809 = [99809] 18 = [5 13] 19 = [3 5 11] 20 = [] 2017 = [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 97 1129] 22699 = [22699] 22699 = [2 22697] 22699 = [3 5 22691] 22699 = [2 3 43 22651] 40355 = [3 139 40213]
Ruby
require "prime"
def prime_partition(x, n)
Prime.each(x).to_a.combination(n).detect{|primes| primes.sum == x}
end
TESTCASES = [[99809, 1], [18, 2], [19, 3], [20, 4], [2017, 24],
[22699, 1], [22699, 2], [22699, 3], [22699, 4], [40355, 3]]
TESTCASES.each do |prime, num|
res = prime_partition(prime, num)
str = res.nil? ? "no solution" : res.join(" + ")
puts "Partitioned #{prime} with #{num} primes: #{str}"
end
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5 + 13 Partitioned 19 with 3 primes: 3 + 5 + 11 Partitioned 20 with 4 primes: no solution Partitioned 2017 with 24 primes: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2 + 22697 Partitioned 22699 with 3 primes: 3 + 5 + 22691 Partitioned 22699 with 4 primes: 2 + 3 + 43 + 22651 Partitioned 40355 with 3 primes: 3 + 139 + 40213
Rust
// main.rs
mod bit_array;
mod prime_sieve;
use prime_sieve::PrimeSieve;
fn find_prime_partition(
sieve: &PrimeSieve,
number: usize,
count: usize,
min_prime: usize,
primes: &mut Vec<usize>,
index: usize,
) -> bool {
if count == 1 {
if number >= min_prime && sieve.is_prime(number) {
primes[index] = number;
return true;
}
return false;
}
for p in min_prime..number {
if sieve.is_prime(p)
&& find_prime_partition(sieve, number - p, count - 1, p + 1, primes, index + 1)
{
primes[index] = p;
return true;
}
}
false
}
fn print_prime_partition(sieve: &PrimeSieve, number: usize, count: usize) {
let mut primes = vec![0; count];
if !find_prime_partition(sieve, number, count, 2, &mut primes, 0) {
println!("{} cannot be partitioned into {} primes.", number, count);
} else {
print!("{} = {}", number, primes[0]);
for i in 1..count {
print!(" + {}", primes[i]);
}
println!();
}
}
fn main() {
let s = PrimeSieve::new(100000);
print_prime_partition(&s, 99809, 1);
print_prime_partition(&s, 18, 2);
print_prime_partition(&s, 19, 3);
print_prime_partition(&s, 20, 4);
print_prime_partition(&s, 2017, 24);
print_prime_partition(&s, 22699, 1);
print_prime_partition(&s, 22699, 2);
print_prime_partition(&s, 22699, 3);
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
}
// prime_sieve.rs
use crate::bit_array;
pub struct PrimeSieve {
composite: bit_array::BitArray,
}
impl PrimeSieve {
pub fn new(limit: usize) -> PrimeSieve {
let mut sieve = PrimeSieve {
composite: bit_array::BitArray::new(limit / 2),
};
let mut p = 3;
while p * p <= limit {
if !sieve.composite.get(p / 2 - 1) {
let inc = p * 2;
let mut q = p * p;
while q <= limit {
sieve.composite.set(q / 2 - 1, true);
q += inc;
}
}
p += 2;
}
sieve
}
pub fn is_prime(&self, n: usize) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
!self.composite.get(n / 2 - 1)
}
}
// bit_array.rs
pub struct BitArray {
array: Vec<u32>,
}
impl BitArray {
pub fn new(size: usize) -> BitArray {
BitArray {
array: vec![0; (size + 31) / 32],
}
}
pub fn get(&self, index: usize) -> bool {
let bit = 1 << (index & 31);
(self.array[index >> 5] & bit) != 0
}
pub fn set(&mut self, index: usize, new_val: bool) {
let bit = 1 << (index & 31);
if new_val {
self.array[index >> 5] |= bit;
} else {
self.array[index >> 5] &= !bit;
}
}
}
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
Scala
object PartitionInteger {
def sieve(nums: LazyList[Int]): LazyList[Int] =
LazyList.cons(nums.head, sieve((nums.tail) filter (_ % nums.head != 0)))
// An 'infinite' stream of primes, lazy evaluation and memo-ized
private val oddPrimes = sieve(LazyList.from(3, 2))
private val primes = sieve(2 #:: oddPrimes).take(3600 /*50_000*/)
private def findCombo(k: Int, x: Int, m: Int, n: Int, combo: Array[Int]): Boolean = {
var foundCombo = combo.map(i => primes(i)).sum == x
if (k >= m) {
if (foundCombo) {
val s: String = if (m > 1) "s" else ""
printf("Partitioned %5d with %2d prime%s: ", x, m, s)
for (i <- 0 until m) {
print(primes(combo(i)))
if (i < m - 1) print('+') else println()
}
}
} else for (j <- 0 until n if k == 0 || j > combo(k - 1)) {
combo(k) = j
if (!foundCombo) foundCombo = findCombo(k + 1, x, m, n, combo)
}
foundCombo
}
private def partition(x: Int, m: Int): Unit = {
val n: Int = primes.count(it => it <= x)
if (n < m) throw new IllegalArgumentException("Not enough primes")
if (!findCombo(0, x, m, n, new Array[Int](m)))
printf("Partitioned %5d with %2d prime%s: (not possible)\n", x, m, if (m > 1) "s" else " ")
}
def main(args: Array[String]): Unit = {
partition(99809, 1)
partition(18, 2)
partition(19, 3)
partition(20, 4)
partition(2017, 24)
partition(22699, 1)
partition(22699, 2)
partition(22699, 3)
partition(22699, 4)
partition(40355, 3)
}
}
SETL
program primes_partition;
tests := [[99809,1], [18,2], [19,3], [20,4], [2017,24],
[22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
loop for [x, n] in tests do
nprint("Partitioned",x,"with",n,"primes:");
if (p := partition(x,n)) = om then
print(" not possible");
else
print(" " + (+/["+" + str pr : pr in p])(2..));
end if;
end loop;
proc partition(x,n);
return findpart(x,n,sieve(x));
end proc;
proc findpart(x,n,nums);
if n=1 then
return if x in nums then [x] else om end;
end if;
loop while nums /= [] do
k fromb nums;
if (l := findpart(x-k, n-1, nums)) /= om then
return [k] + l;
end if;
end loop;
return om;
end proc;
proc sieve(n);
primes := [1..n];
primes(1) := om;
loop for p in [2..floor sqrt n] do
loop for c in [p*p, p*p+p..n] do
primes(c) := om;
end loop;
end loop;
return [p : p in primes | p /= om];
end proc;
end program;
- Output:
Partitioned 99809 with 1 primes: 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: not possible Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 primes: 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
Sidef
func prime_partition(num, parts) {
if (parts == 1) {
return (num.is_prime ? [num] : [])
}
num.primes.combinations(parts, {|*c|
return c if (c.sum == num)
})
return []
}
var tests = [
[ 18, 2], [ 19, 3], [ 20, 4],
[99807, 1], [99809, 1], [ 2017, 24],
[22699, 1], [22699, 2], [22699, 3],
[22699, 4], [40355, 3],
]
for num,parts (tests) {
say ("Partition %5d into %2d prime piece" % (num, parts),
parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible')
}
- Output:
Partition 18 into 2 prime pieces: 5+13 Partition 19 into 3 prime pieces: 3+5+11 Partition 20 into 4 prime pieces: not possible Partition 99807 into 1 prime piece: not possible Partition 99809 into 1 prime piece: 99809 Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 into 1 prime piece: 22699 Partition 22699 into 2 prime pieces: 2+22697 Partition 22699 into 3 prime pieces: 3+5+22691 Partition 22699 into 4 prime pieces: 2+3+43+22651 Partition 40355 into 3 prime pieces: 3+139+40213
Swift
import Foundation
class BitArray {
var array: [UInt32]
init(size: Int) {
array = Array(repeating: 0, count: (size + 31)/32)
}
func get(index: Int) -> Bool {
let bit = UInt32(1) << (index & 31)
return (array[index >> 5] & bit) != 0
}
func set(index: Int, value: Bool) {
let bit = UInt32(1) << (index & 31)
if value {
array[index >> 5] |= bit
} else {
array[index >> 5] &= ~bit
}
}
}
class PrimeSieve {
let composite: BitArray
init(size: Int) {
composite = BitArray(size: size/2)
var p = 3
while p * p <= size {
if !composite.get(index: p/2 - 1) {
let inc = p * 2
var q = p * p
while q <= size {
composite.set(index: q/2 - 1, value: true)
q += inc
}
}
p += 2
}
}
func isPrime(number: Int) -> Bool {
if number < 2 {
return false
}
if (number & 1) == 0 {
return number == 2
}
return !composite.get(index: number/2 - 1)
}
}
func findPrimePartition(sieve: PrimeSieve, number: Int,
count: Int, minPrime: Int,
primes: inout [Int], index: Int) -> Bool {
if count == 1 {
if number >= minPrime && sieve.isPrime(number: number) {
primes[index] = number
return true
}
return false
}
if minPrime >= number {
return false
}
for p in minPrime..<number {
if sieve.isPrime(number: p)
&& findPrimePartition(sieve: sieve, number: number - p,
count: count - 1, minPrime: p + 1,
primes: &primes, index: index + 1) {
primes[index] = p
return true
}
}
return false
}
func printPrimePartition(sieve: PrimeSieve, number: Int, count: Int) {
var primes = Array(repeating: 0, count: count)
if !findPrimePartition(sieve: sieve, number: number, count: count,
minPrime: 2, primes: &primes, index: 0) {
print("\(number) cannot be partitioned into \(count) primes.")
} else {
print("\(number) = \(primes[0])", terminator: "")
for i in 1..<count {
print(" + \(primes[i])", terminator: "")
}
print()
}
}
let sieve = PrimeSieve(size: 100000)
printPrimePartition(sieve: sieve, number: 99809, count: 1)
printPrimePartition(sieve: sieve, number: 18, count: 2)
printPrimePartition(sieve: sieve, number: 19, count: 3)
printPrimePartition(sieve: sieve, number: 20, count: 4)
printPrimePartition(sieve: sieve, number: 2017, count: 24)
printPrimePartition(sieve: sieve, number: 22699, count: 1)
printPrimePartition(sieve: sieve, number: 22699, count: 2)
printPrimePartition(sieve: sieve, number: 22699, count: 3)
printPrimePartition(sieve: sieve, number: 22699, count: 4)
printPrimePartition(sieve: sieve, number: 40355, count: 3)
- Output:
99809 = 99809 18 = 5 + 13 19 = 3 + 5 + 11 20 cannot be partitioned into 4 primes. 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 22699 = 22699 22699 = 2 + 22697 22699 = 3 + 5 + 22691 22699 = 2 + 3 + 43 + 22651 40355 = 3 + 139 + 40213
VBScript
' Partition an integer X into N primes
dim p(),a(32),b(32),v,g: redim p(64)
what="99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 3"
t1=split(what," ")
for j=0 to ubound(t1)
t2=split(t1(j)): x=t2(0): n=t2(1)
t3=split(x,"-"): x=clng(t3(0))
if ubound(t3)=1 then y=clng(t3(1)) else y=x
t3=split(n,"-"): n=clng(t3(0))
if ubound(t3)=1 then m=clng(t3(1)) else m=n
genp y 'generate primes in p
for g=x to y
for q=n to m: part: next 'q
next 'g
next 'j
sub genp(high)
p(1)=2: p(2)=3: c=2: i=p(c)+2
do 'i
k=2: bk=false
do while k*k<=i and not bk 'k
if i mod p(k)=0 then bk=true
k=k+1
loop 'k
if not bk then
c=c+1: if c>ubound(p) then redim preserve p(ubound(p)+8)
p(c)=i
end if
i=i+2
loop until p(c)>high 'i
end sub 'genp
sub getp(z)
if a(z)=0 then w=z-1: a(z)=a(w)
a(z)=a(z)+1: w=a(z): b(z)=p(w)
end sub 'getp
function list()
w=b(1)
if v=g then for i=2 to q: w=w&"+"&b(i): next else w="(not possible)"
list="primes: "&w
end function 'list
sub part()
for i=lbound(a) to ubound(a): a(i)=0: next 'i
for i=1 to q: call getp(i): next 'i
do while true: v=0: bu=false
for s=1 to q
v=v+b(s)
if v>g then
if s=1 then exit do
for k=s to q: a(k)=0: next 'k
for r=s-1 to q: call getp(r): next 'r
bu=true: exit for
end if
next 's
if not bu then
if v=g then exit do
if v<g then call getp(q)
end if
loop
wscript.echo "partition "&g&" into "&q&" "&list
end sub 'part
- Output:
partition 99809 into 1 primes: 99809 partition 18 into 2 primes: 5+13 partition 19 into 3 primes: 3+5+11 partition 20 into 4 primes: (not possible) partition 2017 into 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 partition 22699 into 1 primes: 22699 partition 22699 into 2 primes: 2+22697 partition 22699 into 3 primes: 3+5+22691 partition 22699 into 4 primes: 2+3+43+22651 partition 40355 into 3 primes: 3+139+40213
Visual Basic .NET
' Partition an integer X into N primes - 29/03/2017
Option Explicit On
Module PartitionIntoPrimes
Dim p(8), a(32), b(32), v, g, q As Long
Sub Main()
Dim what, t1(), t2(), t3(), xx, nn As String
Dim x, y, n, m As Long
what = "99809 1 18 2 19 3 20 4 2017 24 22699 1-4 40355 3"
t1 = Split(what, " ")
For j = 0 To UBound(t1)
t2 = Split(t1(j)) : xx = t2(0) : nn = t2(1)
t3 = Split(xx, "-") : x = CLng(t3(0))
If UBound(t3) = 1 Then y = CLng(t3(1)) Else y = x
t3 = Split(nn, "-") : n = CLng(t3(0))
If UBound(t3) = 1 Then m = CLng(t3(1)) Else m = n
genp(y) 'generate primes in p
For g = x To y
For q = n To m : part() : Next 'q
Next 'g
Next 'j
End Sub 'Main
Sub genp(high As Long)
Dim c, i, k As Long
Dim bk As Boolean
p(1) = 2 : p(2) = 3 : c = 2 : i = p(c) + 2
Do 'i
k = 2 : bk = False
Do While k * k <= i And Not bk 'k
If i Mod p(k) = 0 Then bk = True
k = k + 1
Loop 'k
If Not bk Then
c = c + 1 : If c > UBound(p) Then ReDim Preserve p(UBound(p) + 8)
p(c) = i
End If
i = i + 2
Loop Until p(c) > high 'i
End Sub 'genp
Sub getp(z As Long)
Dim w As Long
If a(z) = 0 Then w = z - 1 : a(z) = a(w)
a(z) = a(z) + 1 : w = a(z) : b(z) = p(w)
End Sub 'getp
Function list()
Dim w As String
w = b(1)
If v = g Then
For i = 2 To q : w = w & "+" & b(i) : Next
Else
w = "(not possible)"
End If
Return "primes: " & w
End Function 'list
Sub part()
For i = LBound(a) To UBound(a) : a(i) = 0 : Next 'i
For i = 1 To q : Call getp(i) : Next 'i
Do While True : v = 0
For s = 1 To q
v = v + b(s)
If v > g Then
If s = 1 Then Exit Do
For k = s To q : a(k) = 0 : Next 'k
For r = s - 1 To q : Call getp(r) : Next 'r
Continue Do
End If
Next 's
If v = g Then Exit Do
If v < g Then Call getp(q)
Loop
Console.WriteLine("partition " & g & " into " & q & " " & list())
End Sub 'part
End Module 'PartitionIntoPrimes
- Output:
partition 99809 into 1 primes: 99809 partition 18 into 2 primes: 5+13 partition 19 into 3 primes: 3+5+11 partition 20 into 4 primes: (not possible) partition 2017 into 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 partition 22699 into 1 primes: 22699 partition 22699 into 2 primes: 2+22697 partition 22699 into 3 primes: 3+5+22691 partition 22699 into 4 primes: 2+3+43+22651 partition 40355 into 3 primes: 3+139+40213
Wren
The relevant primes are generated here by a sieve.
import "./math" for Int, Nums
import "./fmt" for Fmt
var primes = Int.primeSieve(1e5)
var foundCombo = false
var findCombo // recursive
findCombo = Fn.new { |k, x, m, n, combo|
if (k >= m) {
if (Nums.sum(combo.map { |i| primes[i] }.toList) == x) {
var s = (m > 1) ? "s" : ""
Fmt.write("Partitioned $5d with $2d prime$s: ", x, m, s)
for (i in 0...m) {
System.write(primes[combo[i]])
System.write((i < m - 1) ? "+" : "\n")
}
foundCombo = true
}
} else {
for (j in 0...n) {
if (k == 0 || j > combo[k - 1]) {
combo[k] = j
if (!foundCombo) findCombo.call(k + 1, x, m, n, combo)
}
}
}
}
var partition = Fn.new { |x, m|
if (x < 2 || m < 1 || m >= x) Fiber.abort("Invalid argument(s)")
var n = primes.where { |p| p <= x }.count
if (n < m) Fiber.abort("Not enough primes")
var combo = List.filled(m, 0)
foundCombo = false
findCombo.call(0, x, m, n, combo)
if (!foundCombo) {
var s = (m > 1) ? "s" : ""
Fmt.print("Partitioned $5d with $2d prime$s: (not possible)", x, m, s)
}
}
var a = [
[99809, 1],
[18, 2],
[19, 3],
[20, 4],
[2017, 24],
[22699, 1],
[22699, 2],
[22699, 3],
[22699, 4],
[40355, 3]
]
for (p in a) partition.call(p[0], p[1])
- Output:
Partitioned 99809 with 1 prime : 99809 Partitioned 18 with 2 primes: 5+13 Partitioned 19 with 3 primes: 3+5+11 Partitioned 20 with 4 primes: (not possible) Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partitioned 22699 with 1 prime : 22699 Partitioned 22699 with 2 primes: 2+22697 Partitioned 22699 with 3 primes: 3+5+22691 Partitioned 22699 with 4 primes: 2+3+43+22651 Partitioned 40355 with 3 primes: 3+139+40213
zkl
Using the prime generator from task Extensible prime generator#zkl.
// Partition integer N into M unique primes
fcn partition(N,M,idx=0,ps=List()){
var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve);
var [const] primes=List();
while(sieve.peek()<=N){ primes.append(sieve.next()) }
if(M<2){
z:=primes.find(N);
return(if(Void!=z and z>=idx) ps.append(N) else Void);
}
foreach z in ([idx..primes.len()-1]){
p:=primes[z];
if(p<=N and self.fcn(N-p,M-1,z+1,ps)) return(ps.insert(0,p));
if(p>N) break;
}
Void // no solution
}
foreach n,m in (T( T(18,2),T(19,3),T(99809,1),T(20,4),T(2017,24),
T(22699,1),T(22699,2),T(22699,3),T(22699,4),T(40355,3), )){
ps:=partition(n,m);
if(ps) println("Partition %d with %d prime(s): %s".fmt(n,m,ps.concat("+")));
else println("Can not partition %d with %d prime(s)".fmt(n,m));
}
- Output:
Partition 18 with 2 prime(s): 5+13 Partition 19 with 3 prime(s): 3+5+11 Partition 99809 with 1 prime(s): 99809 Can not partition 20 with 4 prime(s) Partition 2017 with 24 prime(s): 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129 Partition 22699 with 1 prime(s): 22699 Partition 22699 with 2 prime(s): 2+22697 Partition 22699 with 3 prime(s): 3+5+22691 Partition 22699 with 4 prime(s): 2+3+43+22651 Partition 40355 with 3 prime(s): 3+139+40213