Partition an integer x into n primes: Difference between revisions

 

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

 

The output could/should be shown in a format such as:

 

 

::*   Use any spacing that may be appropriate for the display.

::*   You need not validate the input(s).

::*   You only need to show one solution.

 

:*   [[Sequence of primes by trial division]]

<br><br>

 

=={{header|C++}}==

{{trans|D}}

#include <functional>

#include <iostream>

 

return 0;

{{out}}

<pre>Partitioned 99809 with 1 prime 99809

Partitioned 40355 with 3 primes 3+139+40213</pre>

 

 

 

 

 

 

 

 

{{out}}

 

=={{header|D}}==

{{trans|Kotlin}}

import std.range : take;

import std.stdio;

partition(p[0], p[1]);

}

 

{{out}}

=={{header|F_Sharp|F#}}==

This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]

// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017

let rcTask n ng =

|Some n->printfn "%d is the sum of %A" ng n

|_ ->printfn "No Solution"

{{out}}

<pre>

 

=={{header|Factor}}==

math.parser math.primes sequences ;

 

{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699

4 40355 3 } 2 group

{{out}}

<pre>

Partitioned 22699 with 4 primes: 2+3+43+22651

Partitioned 40355 with 3 primes: 3+139+40213

</pre>

 

{{trans|Kotlin}}

... though uses a sieve to generate the relevant primes.

 

import (

}

}

 

{{out}}

 

=={{header|Haskell}}==

 

| n <= 1 =

[ x

where

ps = takeWhile (<= x) primes

[ x

| x `elem` ps_ ]

where

 

main :: IO ()

main =

mapM_ putStrLn $

(\(x, n) ->

concat

[ [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24)]

, [(40355, 3)]

]

 

justifyLeft :: Int -> Char -> String -> String

{{Out}}

<pre>(99809,1) -> 99809

 

=={{header|J}}==

load 'format/printf'

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

 

 

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.stream.IntStream;

 

partition(40355, 3);

}

{{out}}

<pre>Partitioned 99809 with 1 prime: 99809

Partitioned 40355 with 3 primes: 3+139+40213</pre>

 

=={{header|Julia}}==

{{trans|Sidef}}

 

function primepartition(x::Int64, n::Int64)

println("Partition of ", x, " into ", n, " primes: ",

isempty(ans) ? "impossible" : join(ans, " + "))

 

{{output}}

 

=={{header|Kotlin}}==

 

// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning

)

for (p in a) partition(p.first, p.second)

 

{{out}}

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>

delete char (str.length+1-delim.length) to str.length of str

return str

 

_global.sieve = script("sieve").new()

 

showPrimePartition(22699, 3)

showPrimePartition(22699, 4)

 

{{out}}

</pre>

 

 

 

 

 

 

 

 

 

{{out}}

 

=={{header|PARI/GP}}==

{

if(n==1, return(if(isprime(x) && mn<=x, [x], 0)));

}

V=[[99809,1], [18,2], [19,3], [20,4], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];

{{out}}

<pre>Partitioned 99809 with 1 prime: 99809

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}}

 

sub prime_partition {

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";

{{out}}

<pre>

</pre>

 

 

 

 

 

 

 

 

{{out}}

<pre>

</pre>

 

=={{header|Python}}==

 

def isP(n):

return True

return False

 

def genP(n):

p = [2]

return p

 

for n, cnt in data:

ci = iter(cmb(genP(n), cnt))

while True:

c = next(ci)

break

{{out}}

 

=={{header|Racket}}==

(require math/number-theory)

 

(report-partition 22699 3)

(report-partition 22699 4)

 

{{out}}

partition 40355 with 3 primes: 3 + 139 + 40213</pre>

 

=={{header|REXX}}==

Usage note: &nbsp; entering ranges of &nbsp; '''X''' &nbsp; and &nbsp; '''N''' &nbsp; numbers (arguments) from the command line:

which means: &nbsp; partition all integers (inclusive) from &nbsp; '''X''' ──► '''Y''' &nbsp; with &nbsp; '''N''' ──► '''M''' &nbsp; primes.

<br>The &nbsp; ''to'' &nbsp; number &nbsp; ('''Y''' &nbsp; or &nbsp; '''M''') &nbsp; can be omitted.

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.*/

call genP y /*generate Y number of primes. */

end /*until*/

exit 0 /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

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. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

getP: procedure expose i. p. @.; parse arg z /*bump the prime in the partition list.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the input of: &nbsp; <tt> 99809 1 &nbsp; 18 2 &nbsp; 19 3 &nbsp;20 4 &nbsp; 2017 24 &nbsp; 22699 1-4 &nbsp; 40355 </tt>}}

<pre>

 

=={{header|Ring}}==

# Project : Partition an integer X into N primes

 

next

return items

Output:

<pre>

 

=={{header|Ruby}}==

 

def prime_partition(x, n)

puts "Partitioned #{prime} with #{num} primes: #{str}"

end

{{out}}

<pre>Partitioned 99809 with 1 primes: 99809

Partitioned 40355 with 3 primes: 3 + 139 + 40213

</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

 

if (parts == 1) {

say ("Partition %5d into %2d prime piece" % (num, parts),

parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible')

{{out}}

Partition 19 into 3 prime pieces: 3+5+11

Partition 20 into 4 prime pieces: not possible

Partition 22699 into 3 prime pieces: 3+5+22691

Partition 22699 into 4 prime pieces: 2+3+43+22651

</pre>

 

=={{header|VBScript}}==

{{trans|Rexx}}

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"

wscript.echo "partition "&g&" into "&q&" "&list

end sub 'part

{{out}}

<pre>

{{trans|Rexx}}

{{works with|Visual Basic .NET|2011}}

Option Explicit On

 

 

End Module 'PartitionIntoPrimes

{{out}}

<pre>

</pre>

 

 

=={{header|zkl}}==

Using the prime generator from task [[Extensible prime generator#zkl]].

fcn partition(N,M,idx=0,ps=List()){

var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve);

}

Void // no solution

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));

{{out}}

<pre>