Partition an integer x into n primes: Difference between revisions
Added C# implementation
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Add missing scope declaration) |
(Added C# implementation) |
||
Line 36:
* [[Factors of a Mersenne number]]
* [[Sequence of primes by trial division]]
=={{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 = Combinations(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[]> Combinations(int count, int[] input) {
int index = 0;
int[] helper = new int[count];
int[] result = new int[count];
do {
for (++index; index < count; ++index) helper[index] = helper[index - 1] + 1;
for (int i = 0; i < count; ++i) result[i] = input[helper[i]];
yield return result; //Note this returns the same (modified) array each time, but for this problem that's OK
index = count - 1;
for (int i = 0; i < count; ++i, --index) {
helper[index]++;
if (helper[index] + i < input.Length) break;
}
} while (index >= 0);
}
}</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}}==
| |||