Partition an integer x into n primes: Difference between revisions

=={{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>