Jump to content

Partition an integer x into n primes: Difference between revisions

Partition an integer x into n primes (view source)

Revision as of 01:02, 28 August 2022

1,251 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (→‎{{header|Phix}}: syntax coloured)
m (syntax highlighting fixup automation)
Line 45:
{{trans|D}}
 
<langsyntaxhighlight lang="11l">F is_prime(a)
R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0)))
 
Line 86:
 
L(n, cnt) data
partition(n, cnt)</langsyntaxhighlight>
 
{{out}}
Line 104:
=={{header|C}}==
{{works with|C99}}
<langsyntaxhighlight lang="c">#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
Line 232:
sieve_destroy(&s);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 250:
=={{header|C sharp}}==
{{works with|C sharp|7}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections;
using System.Collections.Generic;
Line 327:
}
 
}</langsyntaxhighlight>
{{out}}
<pre>
Line 344:
=={{header|C++}}==
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <functional>
#include <iostream>
Line 482:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 prime 99809
Line 497:
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight Dlang="d">import std.array : array;
import std.range : take;
import std.stdio;
Line 613:
partition(p[0], p[1]);
}
}</langsyntaxhighlight>
 
{{out}}
Line 629:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Partition an integer as the sum of n primes. Nigel Galloway: November 27th., 2017
let rcTask n ng =
Line 639:
|Some n->printfn "%d is the sum of %A" ng n
|_ ->printfn "No Solution"
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 655:
 
=={{header|Factor}}==
<langsyntaxhighlight lang="factor">USING: formatting fry grouping kernel math.combinatorics
math.parser math.primes sequences ;
 
Line 668:
{ 99809 1 18 2 19 3 20 4 2017 24 22699 1 22699 2 22699 3 22699
4 40355 3 } 2 group
[ first2 2dup partition print-partition ] each</langsyntaxhighlight>
{{out}}
<pre>
Line 686:
{{trans|Kotlin}}
... though uses a sieve to generate the relevant primes.
<langsyntaxhighlight lang="go">package main
 
import (
Line 797:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 814:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.List (delete, intercalate)
import Data.Numbers.Primes (primes)
import Data.Bool (bool)
Line 858:
------------------------- GENERIC -------------------------
justifyLeft :: Int -> Char -> String -> String
justifyLeft n c s = take n (s ++ replicate n c)</langsyntaxhighlight>
{{Out}}
<pre>(99809,1) -> 99809
Line 872:
 
=={{header|J}}==
<syntaxhighlight lang="j">
<lang j>
load 'format/printf'
Line 914:
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
</syntaxhighlight>
</lang>
 
 
Line 933:
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.util.Arrays;
import java.util.stream.IntStream;
 
Line 1,009:
partition(40355, 3);
}
}</langsyntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 prime: 99809
Line 1,026:
 
'''Prime-number functions'''
<langsyntaxhighlight lang="jq">
# Is the input integer a prime?
def is_prime:
Line 1,071:
| primes | if . > $x then break $out else . end;
 
</syntaxhighlight>
</lang>
'''Helper function'''
<langsyntaxhighlight lang="jq"># Emit a stream consisting of arrays, a, of $n items from the input array,
# preserving order, subject to (a|add) == $sum
def take($n; $sum):
Line 1,086:
end
end;
[$n, ., $sum] | take;</langsyntaxhighlight>
 
'''Partitioning an integer into $n primes'''
<langsyntaxhighlight lang="jq"># This function emits a possibly empty stream of arrays.
# Assuming $primes is primes(.), each array corresponds to a
# partition of the input into $n distinct primes.
Line 1,125:
else "A partition of \($x) into \($n) parts: \(first($x | primepartition($n)) | pp )"
end;
</syntaxhighlight>
</lang>
 
'''The tasks'''
<langsyntaxhighlight lang="jq">task(18; 2),
task(19; 3),
task(20; 4),
task(2017; 24),
task(22699; [1,2,3,4]),
task(40355; 3)</langsyntaxhighlight>
{{out}}
<pre>
Line 1,147:
=={{header|Julia}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="julia">using Primes, Combinatorics
 
function primepartition(x::Int64, n::Int64)
Line 1,167:
println("Partition of ", x, " into ", n, " primes: ",
isempty(ans) ? "impossible" : join(ans, " + "))
end</langsyntaxhighlight>
 
{{output}}
Line 1,185:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="scala">// version 1.1.2
 
// compiled with flag -Xcoroutines=enable to suppress 'experimental' warning
Line 1,268:
)
for (p in a) partition(p.first, p.second)
}</langsyntaxhighlight>
 
{{out}}
Line 1,287:
Using the prime generator class "sieve" from task [[Extensible prime generator#Lingo]].
 
<langsyntaxhighlight Lingolang="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>
Line 1,341:
delete char (str.length+1-delim.length) to str.length of str
return str
end</langsyntaxhighlight>
 
<langsyntaxhighlight Lingolang="lingo">-- main
_global.sieve = script("sieve").new()
 
Line 1,355:
showPrimePartition(22699, 3)
showPrimePartition(22699, 4)
showPrimePartition(40355, 3)</langsyntaxhighlight>
 
{{out}}
Line 1,372:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">NextPrimeMemo[n_] := (NextPrimeMemo[n] = NextPrime[n]);(*This improves performance by 30% or so*)
PrimeList[count_] := Prime/@Range[count];(*Just a helper to create an initial list of primes of the desired length*)
AppendPrime[list_] := Append[list,NextPrimeMemo[Last@list]];(*Another helper that makes creating the next candidate less verbose*)
Line 1,412:
TimedResults = ReleaseHold[Hold[AbsoluteTiming[FormatResult[PrimePartition @@ #, Last@#]]] & /@TestCases](*I thought it would be interesting to include the timings, which are in seconds*)
 
TimedResults // TableForm</langsyntaxhighlight>
 
 
Line 1,428:
 
=={{header|Nim}}==
<langsyntaxhighlight Nimlang="nim">import math, sugar
 
const N = 100_000
Line 1,475:
echo n, " cannot be partitionned into ", k, " prime", plural(k)
else:
echo n, " = ", part.join(" + ")</langsyntaxhighlight>
 
{{out}}
Line 1,490:
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">partDistinctPrimes(x,n,mn=2)=
{
if(n==1, return(if(isprime(x) && mn<=x, [x], 0)));
Line 1,525:
}
V=[[99809,1], [18,2], [19,3], [20,4], [2017,24], [22699,1], [22699,2], [22699,3], [22699,4], [40355,3]];
for(i=1,#V, call(displayNicely, V[i]))</langsyntaxhighlight>
{{out}}
<pre>Partitioned 99809 with 1 prime: 99809
Line 1,541:
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}}
<langsyntaxhighlight lang="perl">use ntheory ":all";
 
sub prime_partition {
Line 1,555:
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";
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,572:
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (join(fmt))</span>
Line 1,609:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Partition %d into %d primes: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,626:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<langsyntaxhighlight lang="prolog">prime_partition(N, 1, [N], Min):-
is_prime(N),
N > Min,
Line 1,669:
print_prime_partition(22699, 3),
print_prime_partition(22699, 4),
print_prime_partition(40355, 3).</langsyntaxhighlight>
 
Module for finding prime numbers up to some limit:
<langsyntaxhighlight lang="prolog">:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.
 
Line 1,713:
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</langsyntaxhighlight>
 
{{out}}
Line 1,730:
 
=={{header|Python}}==
<langsyntaxhighlight Pythonlang="python">from itertools import combinations as cmb
 
 
Line 1,764:
except StopIteration:
print(repr((n, cnt)) + " -> Not possible")
break</langsyntaxhighlight>
{{out}}
<pre>(99809, 1) -> 99809
Line 1,778:
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
(require math/number-theory)
 
Line 1,810:
(report-partition 22699 3)
(report-partition 22699 4)
(report-partition 40355 3))</langsyntaxhighlight>
 
{{out}}
Line 1,829:
{{works with|Rakudo|2018.10}}
 
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
 
Line 1,846:
say (sprintf "Partition %5d into %2d prime piece", $number, $parts),
$parts == 1 ?? ': ' !! 's: ', join '+', partition($number, $parts) || 'not possible'
}</langsyntaxhighlight>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Line 1,866:
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.
<langsyntaxhighlight lang="rexx">/*REXX program partitions integer(s) (greater than unity) into N primes. */
parse arg what /*obtain an optional list from the C.L.*/
 
Line 1,917:
end /*!*/ /* [↑] Is sum too low? Bump a prime.*/
say 'partitioned' center(g,9) "into" center(q, 5) list()
return</langsyntaxhighlight>
{{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>
Line 1,933:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Partition an integer X into N primes
 
Line 2,005:
next
return items
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,021:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">require "prime"
 
def prime_partition(x, n)
Line 2,035:
puts "Partitioned #{prime} with #{num} primes: #{str}"
end
</syntaxhighlight>
</lang>
{{out}}
<pre>Partitioned 99809 with 1 primes: 99809
Line 2,051:
=={{header|Rust}}==
{{trans|C}}
<langsyntaxhighlight lang="rust">// main.rs
mod bit_array;
mod prime_sieve;
Line 2,108:
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="rust">// prime_sieve.rs
use crate::bit_array;
 
Line 2,145:
!self.composite.get(n / 2 - 1)
}
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="rust">// bit_array.rs
pub struct BitArray {
array: Vec<u32>,
Line 2,170:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,187:
 
=={{header|Scala}}==
<langsyntaxhighlight Scalalang="scala">object PartitionInteger {
 
def sieve(nums: LazyList[Int]): LazyList[Int] =
Line 2,235:
}
 
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">func prime_partition(num, parts) {
 
if (parts == 1) {
Line 2,262:
say ("Partition %5d into %2d prime piece" % (num, parts),
parts == 1 ? ': ' : 's: ', prime_partition(num, parts).join('+') || 'not possible')
}</langsyntaxhighlight>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Line 2,278:
=={{header|Swift}}==
{{trans|Rust}}
<langsyntaxhighlight lang="swift">import Foundation
 
class BitArray {
Line 2,381:
printPrimePartition(sieve: sieve, number: 22699, count: 3)
printPrimePartition(sieve: sieve, number: 22699, count: 4)
printPrimePartition(sieve: sieve, number: 40355, count: 3)</langsyntaxhighlight>
 
{{out}}
Line 2,399:
=={{header|VBScript}}==
{{trans|Rexx}}
<langsyntaxhighlight lang="vb">' Partition an integer X into N primes
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"
Line 2,462:
wscript.echo "partition "&g&" into "&q&" "&list
end sub 'part
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,480:
{{trans|Rexx}}
{{works with|Visual Basic .NET|2011}}
<langsyntaxhighlight lang="vbnet">' Partition an integer X into N primes - 29/03/2017
Option Explicit On
 
Line 2,559:
 
End Module 'PartitionIntoPrimes
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,579:
{{libheader|Wren-fmt}}
The relevant primes are generated here by a sieve.
<langsyntaxhighlight lang="ecmascript">import "/math" for Int, Nums
import "/fmt" for Fmt
 
Line 2,632:
[40355, 3]
]
for (p in a) partition.call(p[0], p[1])</langsyntaxhighlight>
 
{{out}}
Line 2,650:
=={{header|zkl}}==
Using the prime generator from task [[Extensible prime generator#zkl]].
<langsyntaxhighlight lang="zkl"> // Partition integer N into M unique primes
fcn partition(N,M,idx=0,ps=List()){
var [const] sieve=Utils.Generator(Import("sieve").postponed_sieve);
Line 2,665:
}
Void // no solution
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">foreach n,m in (T( T(18,2),T(19,3),T(99809,1),T(20,4),T(2017,24),
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));
}</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328085"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information