Partition an integer x into n primes
- Task
Partition a positive integer X into N 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 and 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 the following format:
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.
REXX
<lang rexx>/*REXX program partitions integer(s) (greater than unity) into N primes. */ parse arg what /*obtain an optional list from the C.L.*/
do until what== /*possibly process a series of integers*/
parse var what x n what; parse var x x '-' y /*get possible range and # partitions.*/
parse var n n '-' m /*get possible range and # partitions.*/
if x== | x=="," then x=19 /*Not specified? Then use the default.*/
if y== | y=="," then y=x /* " " " " " " */
if n== | n=="," then n= 3 /* " " " " " " */
if m== | m=="," then m=n /* " " " " " " */
call genP y /*generate Y number of primes. */
do g=x to y /*partition X ───► Y into partitions.*/
do q=n to m; call part; end /*q*/ /*partition G into Q primes. */
end /*g*/
end /*until*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: arg high; @.1=2; @.2=3; #=2 /*get highest prime, assign some vars. */
do 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
/*──────────────────────────────────────────────────────────────────────────────────────*/ lst: _=p.1; if $==g then do j=2 to q; _=_ p.j; end; else _='__(not_possible)'; return _ ser: say; say '***error*** ' arg(1); say; exit 13 /*──────────────────────────────────────────────────────────────────────────────────────*/ 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)'primes:' translate(lst(),"+ ",' _')
return</lang>
{{out|output|text= 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