Partition an integer x into n primes: Difference between revisions
Added Prolog Solution
(→{{header|Mathematica}}: flagged as incomplete.) |
(Added Prolog Solution) |
||
Line 1,221:
Partition 22699 into 4 primes: {2,3,43,22651}
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>
| |||