prolog - 找出一个数的所有自然除数(使用 Prolog)

Question

我想创建一个谓词除数(X，[Y])，如果
X>1 和 Y 是 X 的所有除数的列表，从 X 开始到 1。

我的代码现在看起来像:

divisors(1,[1]).
divisors(X,[Y,Z|Ys]) :- 
    X>0,
    Y is X,
    Y>Z, 
    divides(X,[Z|Ys]).

divides(X,[Y,Z|Ys]) :-
    Y>Z, 
    0 is X mod Y, 
    divides(X,[Z|Ys]).
divides(X,[1]).

但是它有几个问题:

如果询问列表(例如 ?-divisors(10,X))，prolog 会返回错误

?- 除数(X,[Y])。其中 [Y] 是不完整的除数列表是正确的...

盖伊编码器编辑

这个答案是由 OP 提供的，并发布在下面的评论中。

搬到这里让其他人看到它。

divisors(X,R) :- 
  X > 1, 
  divisors(X,1,[],R). 

divisors(X,D,R,R):-
  D>X.

divisors(N,D0,R0,R) :-
  divisors_0(N,D0,R0,R1), 
  D is D0 + 1, 
  divisors(N,D,R1,R). 

divisors_0(N,D,R0,[D|R0]) :-
  divides(N,D). 

divisors_0(N,D,R0,R0).

divides(N,D) :-
  0 is N mod D.

Op还注意到这个版本中的一些错误:

如果我问像 (10,[1,2,3]) 这样的错误语句，它不会终止。

如果我询问像 (X, [10,5,2,1]) 这样的语句，它会抛出错误。 (-> 参数未充分初始化。)

Answer 1

在 Prolog 中，使用回溯并为同一个查询提出多个解决方案是很常见的。因此，我们可以构造一个谓词，将第二个参数与所有除数统一起来，而不是构造一个除数列表。例如:

divisor(N, D) :-
    between(1, N, D),
    0 is N mod D.

这将产生:

?- divisor(12, N).
N = 1 ;
N = 2 ;
N = 3 ;
N = 4 ;
N = 6 ;
N = 12.

上面的算法是一个 O(n) 算法:我们扫描与我们想要获得除数的项目的值成线性关系的除数。我们可以通过扫描到 √n 来轻松地将其改进为 O(√n)，并且每次都产生除数(当然，如果它是除数)和协除数，例如:

emitco(D, _, D).
emitco(D, C, C) :-
    dif(D, C).

divisor(N, R) :-
    UB is floor(sqrt(N)),
    between(1, UB, D),
    0 is N mod D,
    C is N / D,
    emitco(D, C, R).

这仍然会产生正确的答案，但顺序就像一个收敛的交替序列:

?- divisor(12, N).
N = 1 ;
N = 12 ;
N = 2 ;
N = 6 ;
N = 3 ;
N = 4.

?- divisor(16, N).
N = 1 ;
N = 16 ;
N = 2 ;
N = 8 ;
N = 4 ;
false.

我们可以通过使用 findall/3 [swi-doc] 获得除数列表。或 setof/3 [swi-doc] . setof/3甚至会对除数进行排序，因此我们可以实现 divisors/2在 divisor/2 方面:

divisors(N, Ds) :-
    setof(D, divisor(N, D), Ds).

例如:

?- divisors(2, N).
N = [1, 2].

?- divisors(3, N).
N = [1, 3].

?- divisors(5, N).
N = [1, 5].

?- divisors(12, N).
N = [1, 2, 3, 4, 6, 12].

?- divisors(15, N).
N = [1, 3, 5, 15].

我们可以使用 reverse/2 扭转那个结果。