Partition an integer x into n primes: Difference between revisions
Content added Content deleted
(→{{header|Mathematica}}: flagged as incomplete.) |
(Added Prolog Solution) |
||
Line 1,221: | Line 1,221: | ||
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|Prolog}}== |
|||
{{works with|SWI Prolog}} |
|||
<lang prolog>prime_partition(N, 1, [N], Min):- |
|||
is_prime(N), |
|||
N > Min, |
|||
!. |
|||
prime_partition(N, K, [P|Rest], Min):- |
|||
K > 1, |
|||
is_prime(P), |
|||
P > Min, |
|||
P < N, |
|||
K1 is K - 1, |
|||
N1 is N - P, |
|||
prime_partition(N1, K1, Rest, P), |
|||
!. |
|||
prime_partition(N, K, Primes):- |
|||
prime_partition(N, K, Primes, 1). |
|||
print_primes([Prime]):- |
|||
!, |
|||
writef('%w\n', [Prime]). |
|||
print_primes([Prime|Primes]):- |
|||
writef('%w + ', [Prime]), |
|||
print_primes(Primes). |
|||
print_prime_partition(N, K):- |
|||
prime_partition(N, K, Primes), |
|||
!, |
|||
writef('%w = ', [N]), |
|||
print_primes(Primes). |
|||
print_prime_partition(N, K):- |
|||
writef('%w cannot be partitioned into %w primes.\n', [N, K]). |
|||
main:- |
|||
find_prime_numbers(100000), |
|||
print_prime_partition(99809, 1), |
|||
print_prime_partition(18, 2), |
|||
print_prime_partition(19, 3), |
|||
print_prime_partition(20, 4), |
|||
print_prime_partition(2017, 24), |
|||
print_prime_partition(22699, 1), |
|||
print_prime_partition(22699, 2), |
|||
print_prime_partition(22699, 3), |
|||
print_prime_partition(22699, 4), |
|||
print_prime_partition(40355, 3).</lang> |
|||
Module for finding prime numbers up to some limit: |
|||
<lang prolog>:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]). |
|||
:- dynamic is_prime/1. |
|||
find_prime_numbers(N):- |
|||
retractall(is_prime(_)), |
|||
assertz(is_prime(2)), |
|||
init_sieve(N, 3), |
|||
sieve(N, 3). |
|||
init_sieve(N, P):- |
|||
P > N, |
|||
!. |
|||
init_sieve(N, P):- |
|||
assertz(is_prime(P)), |
|||
Q is P + 2, |
|||
init_sieve(N, Q). |
|||
sieve(N, P):- |
|||
P * P > N, |
|||
!. |
|||
sieve(N, P):- |
|||
is_prime(P), |
|||
!, |
|||
S is P * P, |
|||
cross_out(S, N, P), |
|||
Q is P + 2, |
|||
sieve(N, Q). |
|||
sieve(N, P):- |
|||
Q is P + 2, |
|||
sieve(N, Q). |
|||
cross_out(S, N, _):- |
|||
S > N, |
|||
!. |
|||
cross_out(S, N, P):- |
|||
retract(is_prime(S)), |
|||
!, |
|||
Q is S + P, |
|||
cross_out(Q, N, P). |
|||
cross_out(S, N, P):- |
|||
Q is S + P, |
|||
cross_out(Q, N, P).</lang> |
|||
{{out}} |
|||
<pre> |
|||
99809 = 99809 |
|||
18 = 5 + 13 |
|||
19 = 3 + 5 + 11 |
|||
20 cannot be partitioned 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> |
</pre> |
||