Partition an integer x into n primes: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (Thundergnat moved page Partition an integer X into N primes to Partition an integer x into n primes: Follow normal task title capitalization policy) |
(Added Wren) |
||
Line 2,164: | Line 2,164: | ||
partition 22699 into 4 primes: 2+3+43+22651 |
partition 22699 into 4 primes: 2+3+43+22651 |
||
partition 40355 into 3 primes: 3+139+40213 |
partition 40355 into 3 primes: 3+139+40213 |
||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|Wren-math}} |
|||
{{libheader|Wren-fmt}} |
|||
The relevant primes are generated here by a sieve. |
|||
<lang ecmascript>import "/math" for Int, Nums |
|||
import "/fmt" for Fmt |
|||
var primes = Int.primeSieve(1e5) |
|||
var foundCombo = false |
|||
var findCombo // recursive |
|||
findCombo = Fn.new { |k, x, m, n, combo| |
|||
if (k >= m) { |
|||
if (Nums.sum(combo.map { |i| primes[i] }.toList) == x) { |
|||
var s = (m > 1) ? "s" : "" |
|||
Fmt.write("Partitioned $5d with $2d prime$s: ", x, m, s) |
|||
for (i in 0...m) { |
|||
System.write(primes[combo[i]]) |
|||
System.write((i < m - 1) ? "+" : "\n") |
|||
} |
|||
foundCombo = true |
|||
} |
|||
} else { |
|||
for (j in 0...n) { |
|||
if (k == 0 || j > combo[k - 1]) { |
|||
combo[k] = j |
|||
if (!foundCombo) findCombo.call(k + 1, x, m, n, combo) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
var partition = Fn.new { |x, m| |
|||
if (x < 2 || m < 1 || m >= x) Fiber.abort("Invalid argument(s)") |
|||
var n = primes.where { |p| p <= x }.count |
|||
if (n < m) Fiber.abort("Not enough primes") |
|||
var combo = List.filled(m, 0) |
|||
foundCombo = false |
|||
findCombo.call(0, x, m, n, combo) |
|||
if (!foundCombo) { |
|||
var s = (m > 1) ? "s" : "" |
|||
Fmt.print("Partitioned $5d with $2d prime$s: (not possible)", x, m, s) |
|||
} |
|||
} |
|||
var a = [ |
|||
[99809, 1], |
|||
[18, 2], |
|||
[19, 3], |
|||
[20, 4], |
|||
[2017, 24], |
|||
[22699, 1], |
|||
[22699, 2], |
|||
[22699, 3], |
|||
[22699, 4], |
|||
[40355, 3] |
|||
] |
|||
for (p in a) partition.call(p[0], p[1])</lang> |
|||
{{out}} |
|||
<pre> |
|||
Partitioned 99809 with 1 prime : 99809 |
|||
Partitioned 18 with 2 primes: 5+13 |
|||
Partitioned 19 with 3 primes: 3+5+11 |
|||
Partitioned 20 with 4 primes: (not possible) |
|||
Partitioned 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 |
|||
Partitioned 22699 with 1 prime : 22699 |
|||
Partitioned 22699 with 2 primes: 2+22697 |
|||
Partitioned 22699 with 3 primes: 3+5+22691 |
|||
Partitioned 22699 with 4 primes: 2+3+43+22651 |
|||
Partitioned 40355 with 3 primes: 3+139+40213 |
|||
</pre> |
</pre> |
||