Partition an integer x into n primes: Difference between revisions

{{Task|Prime Numbers}}

Show in the '''output''' section the (sum)   '''X'''   and the   '''N'''   primes in ascending order   and separated by plus ('''+''') signs:

<big> &bull; </big> &nbsp; partition '''99809''' with 1 prime.

<big> &bull; </big> &nbsp; partition '''18''' with 2 primes.

<big> &bull; </big> &nbsp; partition '''19''' with 3 primes.

<big> &bull; </big> &nbsp; partition '''20''' with 4 primes.

<big> &bull; </big> &nbsp; partition '''2017''' with 24 primes.

<big> &bull; </big> &nbsp; partition '''22699''' with 1, 2, 3, <u>and</u> 4 primes.

<big> &bull; </big> &nbsp; partition '''40355''' with 3 primes.

Partitioned &nbsp; 19 &nbsp; with &nbsp; 3 &nbsp; primes: &nbsp; 3+5+11

::* &nbsp; Use the lowest primes possible; &nbsp; use &nbsp; '''18 = 5+13''', &nbsp; not: &nbsp; '''18 = 7+11'''.

:* &nbsp; [[countCount in factors]]

:* &nbsp; [[primePrime decomposition]]

:* &nbsp; [[factorsFactors of an integer]]

:* &nbsp; [[Sieve of Eratosthenes]]

:* &nbsp; [[primalityPrimality by trial division]]

:* &nbsp; [[factorsFactors of a Mersenne number]]

:* &nbsp; [[trial factoringFactors of a Mersenne number]]

:* &nbsp; [[sequenceSequence of primes by Trialtrial Divisiondivision]]

=={{header|Haskell11l}}==

partition :: Int ->V Intr ->= [Int2]

| last psx == xlast ps ]

| otherwise = partition_go ps x n

partition_go ps_ x 1 =

partitionsFoundfound p =

let((flip rbool =[] x. -return . (p :)) <*> null)

rs((go =<< partition_ (delete p (. flip takeWhile ps_ . (<>= r) ps_)) r (nx - 1p) (pred n))

-- TEST ------------------------------------------- TEST ---------------------------

(intercalate

" -> "

[ justifyLeft 9 ' ' (show (x, n))

, let xs = partitionpartitions x n

] (tail $ concatMap (('+' :) . show) <$>xs)

, (22699, ) 22699 <$> [1 .. 4]

-- GENERIC ------------------------------------------- GENERIC -------------------------

justifyLeft n c s = take n (s ++ replicate n c)</syntaxhighlight>

<langsyntaxhighlight lang="scala">// version 1.1.2

}</langsyntaxhighlight>

=={{header|Perl 6Lingo}}==

multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! [] } # short circuit for '1' partition

my @these = @$sieve.primes[ ^( @primes.first: * > $number, :k ) ];

for @these.combinations($parts) -> @this { .return @this if @this.sum == $number };

[]()

for (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'

}</langsyntaxhighlight>

<langsyntaxhighlight lang="rexx">/*REXX program partitions integer(s) (greater than unity) into N primes. */

parse var n n '-' m /*get possible" " " " " " range and # partitions.*/

if x=='' | x=="," then x=19 19 /*Not specified? Then use the default.*/

if y=='' | y=="," then y=x x /* " " " " " " */

if n=='' | n=="," then n= 3 3 /* " " " " " " */

if m=='' | m=="," then m=n n /* " " " " " " */

do g=x to y 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 end /*gq*/

genP: arg high; @.1= 2; @.2= 3; #=2 2 /*get highest prime, assign some vars. */

#= # + 1; @.#=j @.#= j /*bump prime count; assign prime to @.*/

end /*j*/; return

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; else _= '__(not_possible)'

the= 'primes:'; if q==1 then the= 'prime: '; return the translate(_,"+ ",' _') end /*j*/

part: i.= 0; do j=1 for q; call getP j; end /*j*/

do !=0 by 0; $=0 end /*!: a DO variable for LEAVE & ITERATEj*/

do !=0 by 0; if $>g then do; if s$==1 0 then leave ! /*perform!: a quickDO variable for LEAVE & exit?ITERATE*/

do s=1 for q; $= $ + do k=p.s /* to[↓] q; is i.k=0;sum of the primes too end /*klarge?*/

if $>g then do; if s==1 then leave ! /*perform a quick do r=s-1 to q; call getP r; end /*rexit?*/

iterate ! do k=s to q; i.k= 0; end /*k*/

do r=s-1 to q; call getP r; end /*r*/

end /*s*/ iterate !

if $==g then leave /*is sum of the primes exactly right ? */end

if $ <gend then do; call getP q; iterate; end/*s*/

if end /*!*/ $==g then leave /*is [↑]sum of the Isprimes sumexactly tooright low? Bump a prime.*/

say 'partitioned' center(g,9) if $ <g then "into"do; call getP center(q,; 5) iterate; list()end

<langsyntaxhighlight lang="ruby">require "prime"

<langsyntaxhighlight lang="vb">' Partition an integer X into N primes

<langsyntaxhighlight lang="vbnet">' Partition an integer X into N primes - 29/03/2017

<langsyntaxhighlight lang="zkl"> // Partition integer N into M unique primes

}</langsyntaxhighlight>

<langsyntaxhighlight lang="zkl">foreach n,m in (T( T(18,2),T(19,3),T(99809,1),T(20,4),T(2017,24),

}</langsyntaxhighlight>