Anonymous user
Partition an integer x into n primes: Difference between revisions
Partition an integer x into n primes (view source)
Revision as of 20:40, 12 March 2021
, 3 years ago→{{header|Nim}}
(Added Swift solution) |
|||
Line 1,208:
Partitioned 20 with 4 primes: impossible
</pre>
=={{header|Nim}}==
<lang Nim>import math, sugar
const N = 100_000
# Fill a sieve of Erathostenes.
var isPrime {.noInit.}: array[2..N, bool]
for item in isPrime.mitems: item = true
for n in 2..int(sqrt(N.toFloat)):
if isPrime[n]:
for k in countup(n * n, N, n):
isPrime[k] = false
# Build list of primes.
let primes = collect(newSeq):
for n in 2..N:
if isPrime[n]: n
proc partition(n, k: int; start = 0): seq[int] =
## Partition "n" in "k" primes starting at position "start" in "primes".
## Return the list of primes or an empty list if partitionning is impossible.
if k == 1:
return if isPrime[n] and n >= primes[start]: @[n] else: @[]
for i in start..primes.high:
let a = primes[i]
if n - a <= 1: break
result = partition(n - a, k - 1, i + 1)
if result.len != 0:
return a & result
when isMainModule:
import strutils
func plural(k: int): string =
if k <= 1: "" else: "s"
for (n, k) in [(99809, 1), (18, 2), (19, 3), (20, 4),
(2017, 24), (22699, 1), (22699, 2),
(22699, 3), (22699, 4), (40355, 3)]:
let part = partition(n, k)
if part.len == 0:
echo n, " cannot be partitionned into ", k, " prime", plural(k)
else:
echo n, " = ", part.join(" + ")</lang>
{{out}}
<pre>99809 = 99809
18 = 5 + 13
19 = 3 + 5 + 11
20 cannot be partitionned into 4 primes
2017 = 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 = 22699
22699 = 2 + 22697
22699 = 3 + 5 + 22691
22699 = 2 + 3 + 43 + 22651
40355 = 3 + 139 + 40213</pre>
=={{header|PARI/GP}}==
| |||