Partition an integer x into n primes: Difference between revisions
Added 11l
m (added bullets to the task requirements.) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 41:
:* [[Sequence of primes by trial division]]
<br><br>
=={{header|11l}}==
{{trans|D}}
<lang 11l>F is_prime(a)
R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0)))
F generate_primes(n)
V r = [2]
V i = 3
L
I is_prime(i)
r.append(i)
I r.len == n
L.break
i += 2
R r
V primes = generate_primes(50'000)
F find_combo(k, x, m, n, &combo)
I k >= m
I sum(combo.map(idx -> :primes[idx])) == x
print(‘Partitioned #5 with #2 #.: ’.format(x, m, I m > 1 {‘primes’} E ‘prime ’), end' ‘’)
L(i) 0 .< m
print(:primes[combo[i]], end' I i < m - 1 {‘+’} E "\n")
R 1B
E
L(j) 0 .< n
I k == 0 | j > combo[k - 1]
combo[k] = j
I find_combo(k + 1, x, m, n, &combo)
R 1B
R 0B
F partition(x, m)
V n = :primes.filter(a -> a <= @x).len
V combo = [0] * m
I !find_combo(0, x, m, n, &combo)
print(‘Partitioned #5 with #2 #.: (not possible)’.format(x, m, I m > 1 {‘primes’} E ‘prime’))
V data = [(99809, 1), (18, 2), (19, 3), (20, 4), (2017, 24),
(22699, 1), (22699, 2), (22699, 3), (22699, 4), (40355, 3)]
L(n, cnt) data
partition(n, cnt)</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>
=={{header|C}}==
| |||