Partition an integer x into n primes: Difference between revisions
Partition an integer x into n primes (view source)
Revision as of 09:48, 10 April 2024
, 1 month agoAdd Cowgol
Not a robot (talk | contribs) (Add SETL) |
Not a robot (talk | contribs) (Add Cowgol) |
||
| (5 intermediate revisions by 2 users not shown) | |||
Line 101:
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}}==
Line 494 ⟶ 704:
Partitioned 22699 with 4 primes 2+3+43+22651
Partitioned 40355 with 3 primes 3+139+40213</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0 = 0 then return(s) end
x1: int := (x0 + s/x0) / 2
while x1 < x0 do
x0, x1 := x1, (x0 + s/x0) / 2
end
return(x0)
end isqrt
primes = proc (n: int) returns (sequence[int])
prime: array[bool] := array[bool]$fill(1, n, true)
prime[1] := false
for p: int in int$from_to(2, isqrt(n)) do
for c: int in int$from_to_by(p*p, n, p) do
prime[c] := false
end
end
pr: array[int] := array[int]$predict(1, n)
for p: int in array[bool]$indexes(prime) do
if prime[p] then array[int]$addh(pr, p) end
end
return(sequence[int]$a2s(pr))
end primes
partition_sum = proc (x, n: int, nums: sequence[int])
returns (sequence[int])
signals (impossible)
if n<=0 cor sequence[int]$empty(nums) then signal impossible end
if n=1 then
for k: int in sequence[int]$elements(nums) do
if x=k then return(sequence[int]$[x]) end
end
signal impossible
end
k: int := sequence[int]$bottom(nums)
rest: sequence[int] := sequence[int]$reml(nums)
return(sequence[int]$addl(partition_sum(x-k, n-1, rest), k))
except when impossible:
return(partition_sum(x, n, rest))
resignal impossible
end
end partition_sum
prime_partition = proc (x, n: int)
returns (sequence[int])
signals (impossible)
return(partition_sum(x, n, primes(x))) resignal impossible
end prime_partition
format_sum = proc (nums: sequence[int]) returns (string)
result: string := ""
for n: int in sequence[int]$elements(nums) do
result := result || "+" || int$unparse(n)
end
return(string$rest(result, 2))
end format_sum
start_up = proc ()
test = struct[x: int, n: int]
tests: sequence[test] := sequence[test]$[
test${x:99809,n:1}, test${x:18,n:2}, test${x:19,n:3}, test${x:20,n:4},
test${x:2017,n:24}, test${x:22699,n:1}, test${x:22699,n:2},
test${x:22699,n:3}, test${x:22699,n:4}, test${x:40355,n:3}
]
po: stream := stream$primary_output()
for t: test in sequence[test]$elements(tests) do
stream$puts(po, "Partitioned " || int$unparse(t.x) || " with "
|| int$unparse(t.n) || " primes: ")
stream$putl(po, format_sum(prime_partition(t.x, t.n)))
except when impossible:
stream$putl(po, "not possible.")
end
end
end start_up</syntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible.
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
const MAXPRIM := 100000;
const MAXPRIM_B := (MAXPRIM >> 3) + 1;
var primebits: uint8[MAXPRIM_B];
typedef ENTRY_T is @indexof primebits;
sub pentry(n: uint32): (ent: ENTRY_T, bit: uint8) is
ent := (n >> 3) as ENTRY_T;
bit := (n & 7) as uint8;
end sub;
sub setprime(n: uint32, prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
var one: uint8 := 1;
primebits[ent] := primebits[ent] & ~(one << bit);
primebits[ent] := primebits[ent] | (prime << bit);
end sub;
sub prime(n: uint32): (prime: uint8) is
var ent: ENTRY_T;
var bit: uint8;
(ent, bit) := pentry(n);
prime := (primebits[ent] >> bit) & 1;
end sub;
sub sieve() is
MemSet(&primebits[0], 0xFF, @bytesof primebits);
setprime(0, 0);
setprime(1, 0);
var p: uint32 := 2;
while p*p <= MAXPRIM loop
var c := p*p;
while c <= MAXPRIM loop
setprime(c, 0);
c := c + p;
end loop;
p := p + 1;
end loop;
end sub;
sub nextprime(p: uint32): (r: uint32) is
r := p;
loop
r := r + 1;
if prime(r) != 0 then break; end if;
end loop;
end sub;
sub partition(x: uint32, n: uint8, part: [uint32]): (r: uint8) is
record State is
x: uint32;
n: uint8;
p: uint32;
part: [uint32];
end record;
var stack: State[128];
var sp: @indexof stack := 0;
sub Push(x: uint32, n: uint8, p: uint32, part: [uint32]) is
stack[sp].x := x;
stack[sp].n := n;
stack[sp].p := p;
stack[sp].part := part;
sp := sp + 1;
end sub;
sub Pull(): (x: uint32, n: uint8, p: uint32, part: [uint32]) is
sp := sp - 1;
x := stack[sp].x;
n := stack[sp].n;
p := stack[sp].p;
part := stack[sp].part;
end sub;
r := 0;
Push(x, n, 1, part);
while sp > 0 loop
var p: uint32;
(x, n, p, part) := Pull();
p := nextprime(p);
if x < p then
continue;
end if;
if n == 1 then
if prime(x) != 0 then
r := 1;
[part] := x;
return;
end if;
else
[part] := p;
Push(x, n, p, part);
Push(x-p, n-1, p, @next part);
end if;
end loop;
r := 0;
end sub;
sub showpartition(x: uint32, n: uint8) is
print("Partitioning ");
print_i32(x);
print(" with ");
print_i8(n);
print(" primes: ");
var part: uint32[64];
if partition(x, n, &part[0]) != 0 then
print_i32(part[0]);
var i: @indexof part := 1;
while i < n as @indexof part loop
print_char('+');
print_i32(part[i]);
i := i + 1;
end loop;
else
print("Not possible");
end if;
print_nl();
end sub;
sieve();
record Test is
x: uint32;
n: uint8;
end record;
var tests: Test[] := {
{99809, 1}, {18, 2}, {19, 3}, {20, 4}, {2017, 24},
{22699, 1}, {22699, 2}, {22699, 3}, {22699, 4}, {40355, 3}
};
var test: @indexof tests := 0;
while test < @sizeof tests loop
showpartition(tests[test].x, tests[test].n);
test := test + 1;
end loop;</syntaxhighlight>
{{out}}
<pre>Partitioning 99809 with 1 primes: 99809
Partitioning 18 with 2 primes: 5+13
Partitioning 19 with 3 primes: 3+5+11
Partitioning 20 with 4 primes: Not possible
Partitioning 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioning 22699 with 1 primes: 22699
Partitioning 22699 with 2 primes: 2+22697
Partitioning 22699 with 3 primes: 3+5+22691
Partitioning 22699 with 4 primes: 2+3+43+22651
Partitioning 40355 with 3 primes: 3+139+40213</pre>
=={{header|D}}==
Line 2,064 ⟶ 2,524:
Partition 40355 into 3 prime pieces: 3+139+40213</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Each Test <Tests>>;
};
Tests {
= (99809 1) (18 2) (19 3) (20 4) (2017 24)
(22699 1) (22699 2) (22699 3) (22699 4) (40355 3);
};
Test {
(s.X s.N) =
<Prout 'Partitioned ' <Symb s.X> ' with ' <Symb s.N> ' primes: '
<Format <PrimePartition s.X s.N>>>;
};
Format {
F = 'not possible';
T s.N = <Symb s.N>;
T s.N e.X = <Symb s.N> '+' <Format T e.X>;
};
PrimePartition {
s.X s.N = <Partition s.X s.N <Primes s.X>>;
};
Partition {
s.X 1 e.Nums, e.Nums: {
e.1 s.X e.2 = T s.X;
e.1 = F;
};
s.X s.N = F;
s.X s.N s.Num e.Nums, <Compare s.X s.Num>: '-' =
<Partition s.X s.N e.Nums>;
s.X s.N s.Num e.Nums,
<Partition <- s.X s.Num> <- s.N 1> e.Nums>: {
T e.List = T s.Num e.List;
F = <Partition s.X s.N e.Nums>;
};
};
Primes {
s.N = <Sieve <Iota 2 s.N>>;
};
Iota {
s.End s.End = s.End;
s.Start s.End = s.Start <Iota <+ 1 s.Start> s.End>;
};
Cross {
s.Step e.List = <Cross (s.Step 1) s.Step e.List>;
(s.Step s.Skip) = ;
(s.Step 1) s.Item e.List = X <Cross (s.Step s.Step) e.List>;
(s.Step s.N) s.Item e.List = s.Item <Cross (s.Step <- s.N 1>) e.List>;
};
Sieve {
= ;
X e.List = <Sieve e.List>;
s.N e.List = s.N <Sieve <Cross s.N e.List>>;
};
Each {
s.F = ;
s.F t.X e.R = <Mu s.F t.X> <Each s.F e.R>;
};</syntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Partitioned 18 with 2 primes: 5+13
Partitioned 19 with 3 primes: 3+5+11
Partitioned 20 with 4 primes: not possible
Partitioned 2017 with 24 primes: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partitioned 22699 with 1 primes: 22699
Partitioned 22699 with 2 primes: 2+22697
Partitioned 22699 with 3 primes: 3+5+22691
Partitioned 22699 with 4 primes: 2+3+43+22651
Partitioned 40355 with 3 primes: 3+139+40213</pre>
=={{header|REXX}}==
Usage note: entering ranges of '''X''' and '''N''' numbers (arguments) from the command line:
| |||