Prolog 中的不同素数分区
Distinct Prime Partitions in Prolog
我需要在 Prolog 中列举将给定数字 n 划分为一个或多个不同素数的总和的所有方法，a + b + ... + m
例如：
给定一个整数 n，程序应将适当的和写入标准输出。例如，如果 n = 20，程序可能会打印
2 + 5 + 13
2 + 7 + 11
3 + 17
7 + 13
n可以是任意数，运行次没有限制。
这是我的资料：
partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.
partition(N, [IH|IT], [OH|OT]) :-
N =< 0, fail;
N >= IH, M is N-IH, OH = IH,
partition(M, [IH|IT], OT).
partition(N, [_|IT], Output) :-
N =< 0, fail;
partition(N, IT, Output).
partition(N, Output) :-
generatePrime(N,L),
partition(N, L, Output).
generatePrime(1, []) :- !.
generatePrime(N, X) :-
not(isPrime(N)), !,
Z is N-1,
generatePrime(Z,X).
generatePrime(N, [N | X]) :-
Z is N-1,
generatePrime(Z,X).
isPrime(2).
isPrime(P) :-
P > 2,
isDivisible(P, P-1).
isDivisible(P,X) :-
X > 1,
P mod X =\= 0,
isDivisible(P, X-1).
isDivisible(_, X) :-
1 is X.
目前，我尝试 运行宁这样的事情：
[?- 分区(5, X).
并且我收到 [5] 和 [3,2] 的重复提示。当我使用更大的数字（如 n = 20）时，还会出现另一种类型的问题，因为我会收到带有重复素数的提示，如 [2,2,2,2,2,2,2,2,2,2].
我是 prolog 的新手，我相信可能有更简单的方法来解决这个问题，但我不确定我在代码中哪里出错了。
你还没有...
更大的问题是你打电话的方式 partition/3
partition(5, generatePrime(5,Y), X)
partition/3 期待第二个学期的列表，而不是 generatePrime(5, Y)。
建议你加一个partition/2制作如下
partition(N, Output) :-
generatePrime(N, L),
partition(N, L, Output).
并称这个版本为 partition
partition(5, X)
还有其他问题，因为此调用 return 多次相同的响应（return，在 X、[5] 中四次和 [3,2]两次）。
我会看一下是否发现问题
--- 编辑 ---
抱歉，我在理解带有剪切 (!)、fail 和或 (;) 的 Prolog 代码时遇到了很大的问题。
我想这是我的问题。
我已经按照以下方式修改了你的partition/3
partition(0, _, []).
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, [H | It], Ot).
partition(N, [_ | It], O) :-
N > 0,
partition(N, It, O).
这应该避免重复列表
如果你想避免在同一个列表中出现重复的素数（如果你不接受 [3, 3, 2] 或 [2, 2, 2, 2] 表示 8 因为素数重复），你应该避免重复使用 H（IH 在您的原始代码中）在以下对 partition/3.
的调用中
我的意思是下面的子句
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, [H | It], Ot).
应该变成
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, It, Ot).
这是一个相对有效的答案，在 SWI-Prolog 中使用 library(clpfd)。
你的程序开始时需要 :- use_module(library(clpfd)).。
主谓词：partition/2
这个谓词可以用一种非常简单的方式来描述：
partition(N,Z) :-
findall(P, (P in 2..N, prime(P)), L),
findall(S, ordered_subset_sum(L, S, N), Z).
简而言之：找到 [2,N] 中的所有数字 P，使得它们是质数。我们将这些素数存储在列表 L.
中
然后，我们使用谓词 ordered_subset_sum/3 检查对 L 的有序子集 S 求和得到 N。我们将有效子集存储在 Z 中，这是我们的输出。
ordered_subset_sum/3
ordered_subset_sum([],[],0).
ordered_subset_sum([H|T],[H|T2],N) :-
M #= N - H,
M #>= 0,
ordered_subset_sum(T,T2,M).
ordered_subset_sum([_|T],T2,N) :-
ordered_subset_sum(T,T2,N).
基本情况：一个空列表只能生成一个空子集；空子集的元素之和为0.
第二个子句：我们将列表的头部 H 保留在子集中；因此，我们想要达到的总和 N 减少了 H，结果是 M。如果 M 是负数，那么我们已经知道子集不能和 N ；太大了。
第三条：忽略表头，允许子集生成
prime/1
如果愿意，您可以重复使用谓词 isPrime，例如：
prime(N) :-
indomain(N),
isPrime(N).
但我建议使用更高效的素数检查算法。我提出以下一个，它远非最佳，但比你的效率高得多。它检查你的数字的质数分解是否只有一个元素（只有质数有）。你也可以看看 Julio Di Egidio's Prime-Prolog library.
prime(N) :-
prime_decomposition(N,[_P]).
prime_decomposition(N, Z) :-
N #> 0,
indomain(N),
prime_decomposition_ceiled_square_root(N,SN),
prime_decomposition_1(N, SN, 2, [], Z).
prime_decomposition_1(1, _, _, L, L) :- !.
prime_decomposition_1(N, SN, D, L, LF) :-
(
0 #= N mod D ->
Q #= N // D,
prime_decomposition_ceiled_square_root(Q,SQ),
prime_decomposition_1(Q, SQ, D, [D |L], LF)
;
D1 #= D+1,
(
D1 #> SN ->
LF = [N |L]
;
prime_decomposition_2(N, SN, D1, L, LF)
)
).
prime_decomposition_2(1, _, _, L, L) :- !.
prime_decomposition_2(N, SN, D, L, LF) :-
(
0 #= N mod D ->
Q #= N // D,
prime_decomposition_ceiled_square_root(Q,SQ),
prime_decomposition_2(Q, SQ, D, [D |L], LF);
D1 #= D+2,
(
D1 #> SN ->
LF = [N |L]
;
prime_decomposition_2(N, SN, D1, L, LF)
)
).
prime_decomposition_ceiled_square_root(0, 0).
prime_decomposition_ceiled_square_root(N0, Root) :-
N1 #= N0 - 1,
Max in 0..N1,
R0^2 #= Max,
Root #= Root0 + 1,
fd_sup(R0, Root0).
我需要在 Prolog 中列举将给定数字 n 划分为一个或多个不同素数的总和的所有方法，a + b + ... + m
例如：
给定一个整数 n，程序应将适当的和写入标准输出。例如，如果 n = 20，程序可能会打印
2 + 5 + 13
2 + 7 + 11
3 + 17
7 + 13
n可以是任意数，运行次没有限制。
这是我的资料：
partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.
partition(N, [IH|IT], [OH|OT]) :-
N =< 0, fail;
N >= IH, M is N-IH, OH = IH,
partition(M, [IH|IT], OT).
partition(N, [_|IT], Output) :-
N =< 0, fail;
partition(N, IT, Output).
partition(N, Output) :-
generatePrime(N,L),
partition(N, L, Output).
generatePrime(1, []) :- !.
generatePrime(N, X) :-
not(isPrime(N)), !,
Z is N-1,
generatePrime(Z,X).
generatePrime(N, [N | X]) :-
Z is N-1,
generatePrime(Z,X).
isPrime(2).
isPrime(P) :-
P > 2,
isDivisible(P, P-1).
isDivisible(P,X) :-
X > 1,
P mod X =\= 0,
isDivisible(P, X-1).
isDivisible(_, X) :-
1 is X.
目前，我尝试 运行宁这样的事情：
[?- 分区(5, X).
并且我收到 [5] 和 [3,2] 的重复提示。当我使用更大的数字（如 n = 20）时，还会出现另一种类型的问题，因为我会收到带有重复素数的提示，如 [2,2,2,2,2,2,2,2,2,2].
我是 prolog 的新手，我相信可能有更简单的方法来解决这个问题，但我不确定我在代码中哪里出错了。
你还没有...
更大的问题是你打电话的方式 partition/3
partition(5, generatePrime(5,Y), X)
partition/3 期待第二个学期的列表，而不是 generatePrime(5, Y)。
建议你加一个partition/2制作如下
partition(N, Output) :-
generatePrime(N, L),
partition(N, L, Output).
并称这个版本为 partition
partition(5, X)
还有其他问题，因为此调用 return 多次相同的响应（return，在 X、[5] 中四次和 [3,2]两次）。
我会看一下是否发现问题
--- 编辑 ---
抱歉，我在理解带有剪切 (!)、fail 和或 (;) 的 Prolog 代码时遇到了很大的问题。
我想这是我的问题。
我已经按照以下方式修改了你的partition/3
partition(0, _, []).
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, [H | It], Ot).
partition(N, [_ | It], O) :-
N > 0,
partition(N, It, O).
这应该避免重复列表
如果你想避免在同一个列表中出现重复的素数（如果你不接受 [3, 3, 2] 或 [2, 2, 2, 2] 表示 8 因为素数重复），你应该避免重复使用 H（IH 在您的原始代码中）在以下对 partition/3.
我的意思是下面的子句
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, [H | It], Ot).
应该变成
partition(N, [H | It], [H | Ot]) :-
N >= H,
M is N-H,
partition(M, It, Ot).
这是一个相对有效的答案，在 SWI-Prolog 中使用 library(clpfd)。
你的程序开始时需要 :- use_module(library(clpfd)).。
主谓词：partition/2
这个谓词可以用一种非常简单的方式来描述：
partition(N,Z) :-
findall(P, (P in 2..N, prime(P)), L),
findall(S, ordered_subset_sum(L, S, N), Z).
简而言之：找到 [2,N] 中的所有数字 P，使得它们是质数。我们将这些素数存储在列表 L.
然后，我们使用谓词 ordered_subset_sum/3 检查对 L 的有序子集 S 求和得到 N。我们将有效子集存储在 Z 中，这是我们的输出。
ordered_subset_sum/3
ordered_subset_sum([],[],0).
ordered_subset_sum([H|T],[H|T2],N) :-
M #= N - H,
M #>= 0,
ordered_subset_sum(T,T2,M).
ordered_subset_sum([_|T],T2,N) :-
ordered_subset_sum(T,T2,N).
基本情况：一个空列表只能生成一个空子集；空子集的元素之和为
0.第二个子句：我们将列表的头部
H保留在子集中；因此，我们想要达到的总和N减少了H，结果是M。如果M是负数，那么我们已经知道子集不能和N；太大了。第三条：忽略表头，允许子集生成
prime/1
如果愿意，您可以重复使用谓词 isPrime，例如：
prime(N) :-
indomain(N),
isPrime(N).
但我建议使用更高效的素数检查算法。我提出以下一个，它远非最佳，但比你的效率高得多。它检查你的数字的质数分解是否只有一个元素（只有质数有）。你也可以看看 Julio Di Egidio's Prime-Prolog library.
prime(N) :-
prime_decomposition(N,[_P]).
prime_decomposition(N, Z) :-
N #> 0,
indomain(N),
prime_decomposition_ceiled_square_root(N,SN),
prime_decomposition_1(N, SN, 2, [], Z).
prime_decomposition_1(1, _, _, L, L) :- !.
prime_decomposition_1(N, SN, D, L, LF) :-
(
0 #= N mod D ->
Q #= N // D,
prime_decomposition_ceiled_square_root(Q,SQ),
prime_decomposition_1(Q, SQ, D, [D |L], LF)
;
D1 #= D+1,
(
D1 #> SN ->
LF = [N |L]
;
prime_decomposition_2(N, SN, D1, L, LF)
)
).
prime_decomposition_2(1, _, _, L, L) :- !.
prime_decomposition_2(N, SN, D, L, LF) :-
(
0 #= N mod D ->
Q #= N // D,
prime_decomposition_ceiled_square_root(Q,SQ),
prime_decomposition_2(Q, SQ, D, [D |L], LF);
D1 #= D+2,
(
D1 #> SN ->
LF = [N |L]
;
prime_decomposition_2(N, SN, D1, L, LF)
)
).
prime_decomposition_ceiled_square_root(0, 0).
prime_decomposition_ceiled_square_root(N0, Root) :-
N1 #= N0 - 1,
Max in 0..N1,
R0^2 #= Max,
Root #= Root0 + 1,
fd_sup(R0, Root0).