prolog - 序言中给定数字的质因数列表及其基础知识

Question

实际上，我在学校的任务是找到给定数字的所有素因数并将它们作为列表返回，但我有点挣扎，因为在序言方面我还是个新手。 这是我的代码:

divisible(A, B) :-A mod B =:= 0, !.
divisible(A, B) :-A > B + 1, divisible(A, B + 1).
isPrime(2).
isPrime(A) :-not(divisible(A, 2)).

nextPrime(A, P) :-P is A + 1, isPrime(P),!.
nextPrime(A, P) :-A0 is A + 1,nextPrime(A0, P).

primeFactors(B,L):-primeFactors(B,L,2).

primeFactors(2,[2],_).
primeFactors(3,[3],_).
primeFactors(B,L,C):-B>3, C<B//2, B mod C =:= 0,add_tail(L,C,L1),B1 is B//C, primeFactors(B1,L1,C).
primeFactors(B,L,C):-B>3, C<B//2, nextPrime(C,C1),primeFactors(B,L,C1).

add_tail([],X,[X]).
add_tail([H|T],X,[H|L]):-add_tail(T,X,L).

想法是从 primeFactors/2 开始，然后从那里转发到 primeFactors/3，其中 C 是质数除法器，因此用户更容易调用它。 B 是给定的数字，L 是我要返回的列表。

我应该指出 isPrime、nextPrime 和 add_tail 单独工作时效果非常好。

我在网上看到这个问题有一些解决方案，但我对prolog还只有基本的了解。

Answer 1

使用你的谓词我会这样做:

primeFactors(1,[],_).
primeFactors(B,[C|L],C):-
    B > 1, 
    C =< B, 
    0 is B mod C,
    B1 is B//C, 
    primeFactors(B1,L,C).
primeFactors(B,L,C):-
    B > 1, 
    C < B, 
    0 < B mod C,
    nextPrime(C,C1),
    primeFactors(B,L,C1).

第一行是最终情况:如果达到B==1，则找到了所有因子。在其他情况下，B 必须大于 1。那么有两种情况:当前素数 C 要么是 B 的因数(第二种情况)，要么不是(第三种情况)。
如果C是B的质因数，则C必须小于或等于B。相等的部分对于达到 B==1 的情况很重要。如果是这样，请将 B 除以 C 并继续使用新值。此外，C 必须是素数列表的一部分([C|L] --> 列表的头/尾符号)。

如果C不是B的质因数(第3种情况)，则搜索下一个更高的质因数并继续。

测试:

?- primeFactors(120,L,2).
L = [2, 2, 2, 3, 5] ;
false.

?- primeFactors(7,L,2).
L = [7] ;
false.

?- primeFactors(14,L,2).
L = [2, 7] ;
false.