Rosetta Code

Partition an integer x into n primes: Difference between revisions

Page Discussion

Partition an integer x into n primes (view source)

Revision as of 17:07, 14 March 2020

15 bytes added ,  4 years ago
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Scala contribution added.)
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 41:
:*   [[Sequence of primes by trial division]]
<br><br>
 
=={{header|C sharp}}==
{{works with|C sharp|7}}
<lang csharp>using System;
using System.Collections;
using System.Collections.Generic;
using static System.Linq.Enumerable;
 
public static class Rosetta
{
static void Main()
{
foreach ((int x, int n) in new [] {
(99809, 1),
(18, 2),
(19, 3),
(20, 4),
(2017, 24),
(22699, 1),
(22699, 2),
(22699, 3),
(22699, 4),
(40355, 3)
}) {
Console.WriteLine(Partition(x, n));
}
}
 
public static string Partition(int x, int n) {
if (x < 1 || n < 1) throw new ArgumentOutOfRangeException("Parameters must be positive.");
string header = $"{x} with {n} {(n == 1 ? "prime" : "primes")}: ";
int[] primes = SievePrimes(x).ToArray();
if (primes.Length < n) return header + "not enough primes";
int[] solution = CombinationsOf(n, primes).FirstOrDefault(c => c.Sum() == x);
return header + (solution == null ? "not possible" : string.Join("+", solution);
}
 
static IEnumerable<int> SievePrimes(int bound) {
if (bound < 2) yield break;
yield return 2;
 
BitArray composite = new BitArray((bound - 1) / 2);
int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
for (int i = 0; i < limit; i++) {
if (composite[i]) continue;
int prime = 2 * i + 3;
yield return prime;
for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime) composite[j] = true;
}
for (int i = limit; i < composite.Count; i++) {
if (!composite[i]) yield return 2 * i + 3;
}
}
 
static IEnumerable<int[]> CombinationsOf(int count, int[] input) {
T[] result = new T[count];
foreach (int[] indices in Combinations(input.Length, count)) {
for (int i = 0; i < count; i++) result[i] = input[indices[i]];
yield return result;
}
}
 
static IEnumerable<int[]> Combinations(int n, int k) {
var result = new int[k];
var stack = new Stack<int>();
stack.Push(0);
while (stack.Count > 0) {
int index = stack.Count - 1;
int value = stack.Pop();
while (value < n) {
result[index++] = value++;
stack.Push(value);
if (index == k) {
yield return result;
break;
}
}
}
}
 
}</lang>
{{out}}
<pre>
99809 with 1 prime: 99809
18 with 2 primes: 5+13
19 with 3 primes: 3+5+11
20 with 4 primes: not possible
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
22699 with 1 prime: 22699
22699 with 2 primes: 2+22697
22699 with 3 primes: 3+5+22691
22699 with 4 primes: 2+3+43+22651
40355 with 3 primes: 3+139+40213
</pre>
 
=={{header|C++}}==
Line 194 ⟶ 288:
Partitioned 22699 with 4 primes 2+3+43+22651
Partitioned 40355 with 3 primes 3+139+40213</pre>
 
=={{header|C sharp}}==
{{works with|C sharp|7}}
<lang csharp>using System;
using System.Collections;
using System.Collections.Generic;
using static System.Linq.Enumerable;
 
public static class Rosetta
{
static void Main()
{
foreach ((int x, int n) in new [] {
(99809, 1),
(18, 2),
(19, 3),
(20, 4),
(2017, 24),
(22699, 1),
(22699, 2),
(22699, 3),
(22699, 4),
(40355, 3)
}) {
Console.WriteLine(Partition(x, n));
}
}
 
public static string Partition(int x, int n) {
if (x < 1 || n < 1) throw new ArgumentOutOfRangeException("Parameters must be positive.");
string header = $"{x} with {n} {(n == 1 ? "prime" : "primes")}: ";
int[] primes = SievePrimes(x).ToArray();
if (primes.Length < n) return header + "not enough primes";
int[] solution = CombinationsOf(n, primes).FirstOrDefault(c => c.Sum() == x);
return header + (solution == null ? "not possible" : string.Join("+", solution);
}
 
static IEnumerable<int> SievePrimes(int bound) {
if (bound < 2) yield break;
yield return 2;
 
BitArray composite = new BitArray((bound - 1) / 2);
int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
for (int i = 0; i < limit; i++) {
if (composite[i]) continue;
int prime = 2 * i + 3;
yield return prime;
for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime) composite[j] = true;
}
for (int i = limit; i < composite.Count; i++) {
if (!composite[i]) yield return 2 * i + 3;
}
}
 
static IEnumerable<int[]> CombinationsOf(int count, int[] input) {
T[] result = new T[count];
foreach (int[] indices in Combinations(input.Length, count)) {
for (int i = 0; i < count; i++) result[i] = input[indices[i]];
yield return result;
}
}
 
static IEnumerable<int[]> Combinations(int n, int k) {
var result = new int[k];
var stack = new Stack<int>();
stack.Push(0);
while (stack.Count > 0) {
int index = stack.Count - 1;
int value = stack.Pop();
while (value < n) {
result[index++] = value++;
stack.Push(value);
if (index == k) {
yield return result;
break;
}
}
}
}
 
}</lang>
{{out}}
<pre>
99809 with 1 prime: 99809
18 with 2 primes: 5+13
19 with 3 primes: 3+5+11
20 with 4 primes: not possible
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
22699 with 1 prime: 22699
22699 with 2 primes: 2+22697
22699 with 3 primes: 3+5+22691
22699 with 4 primes: 2+3+43+22651
40355 with 3 primes: 3+139+40213
</pre>
 
=={{header|D}}==
Line 1,072:
-- "Partitioned 40355 with 3 primes: 3+139+40213"
</pre>
 
 
=={{header|Mathematica}}==
Line 1,180 ⟶ 1,179:
Partition 40355 into 3 prime pieces: 3+139+40213
</pre>
 
=={{header|Perl 6}}==
{{works with|Rakudo|2018.10}}
 
<lang perl6>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
 
# short circuit for '1' partition
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! () }
 
multi partition ( Int $number, Int $parts where * > 0 = 2 ) {
my @these = $sieve.primes($number);
for @these.combinations($parts) { .return if .sum == $number };
()
}
 
# TESTING
(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'
}</lang>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Partition 19 into 3 prime pieces: 3+5+11
Partition 20 into 4 prime pieces: not possible
Partition 99807 into 1 prime piece: not possible
Partition 99809 into 1 prime piece: 99809
Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partition 22699 into 1 prime piece: 22699
Partition 22699 into 2 prime pieces: 2+22697
Partition 22699 into 3 prime pieces: 3+5+22691
Partition 22699 into 4 prime pieces: 2+3+43+22651
Partition 40355 into 3 prime pieces: 3+139+40213</pre>
 
=={{header|Phix}}==
Line 1,357 ⟶ 1,322:
partition 22699 with 4 primes: 2 + 3 + 43 + 22651
partition 40355 with 3 primes: 3 + 139 + 40213</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.10}}
 
<lang perl6>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
 
# short circuit for '1' partition
multi partition ( Int $number, 1 ) { $number.is-prime ?? $number !! () }
 
multi partition ( Int $number, Int $parts where * > 0 = 2 ) {
my @these = $sieve.primes($number);
for @these.combinations($parts) { .return if .sum == $number };
()
}
 
# TESTING
(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'
}</lang>
{{out}}
<pre>Partition 18 into 2 prime pieces: 5+13
Partition 19 into 3 prime pieces: 3+5+11
Partition 20 into 4 prime pieces: not possible
Partition 99807 into 1 prime piece: not possible
Partition 99809 into 1 prime piece: 99809
Partition 2017 into 24 prime pieces: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129
Partition 22699 into 1 prime piece: 22699
Partition 22699 into 2 prime pieces: 2+22697
Partition 22699 into 3 prime pieces: 3+5+22691
Partition 22699 into 4 prime pieces: 2+3+43+22651
Partition 40355 into 3 prime pieces: 3+139+40213</pre>
 
=={{header|REXX}}==
Line 1,591:
 
}</lang>
 
=={{header|Sidef}}==
{{trans|Perl}}
Line 1,806 ⟶ 1,807:
partition 40355 into 3 primes: 3+139+40213
</pre>
 
 
=={{header|zkl}}==
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/274678"