Prolog底层运行机制及has_divisor子句调用逻辑咨询

• 归结原理为核心：Prolog将所有事实、规则视为逻辑子句，通过匹配目标与子句头部推导结论，本质是基于一阶逻辑的自动推理。
• 统一（Unification）操作：这是最基础的匹配逻辑，负责将变量与常量、变量与变量绑定。比如把X和5统一，或让X与Y指向同一值，是子句匹配的前提。
• 回溯机制：当当前推导路径失败时，Prolog会回到最近的选择点，尝试其他可能的子句或变量绑定。比如一个目标有多个匹配子句，先试第一个，失败就退回试第二个。
• SLD归结策略：Prolog实际采用的高效归结方式，从目标出发，按顺序匹配子句头部生成新子目标，直到所有子目标满足（成功）或无匹配子句（失败）。
• 知识库式存储：所有事实、规则存储在知识库中，查询时按顺序检索匹配的子句。

先看完整代码：

is_prime(2).
is_prime(3).
is_prime(P):-
    P>3,
    integer(P),
    P mod 2 =\= 0,
    \+ has_divisor(P,3).

has_divisor(N,D):-
    N mod D =:= 0.
has_divisor(N, D):-
    D * D < N,
    D2 is D + 2,
    has_divisor(N, D2).

is_prime/1通过\+ has_divisor(P,3)判断P是否无因数（\+是取反操作，若has_divisor证明失败，则P是素数），has_divisor的两个子句按顺序匹配、失败回溯的逻辑执行：

1. 第一个子句：直接判断整除性
   先检查N mod D =:= 0：如果N能被D整除，直接返回成功，说明N存在因数D，不是素数；若不满足，Prolog会回溯，尝试第二个子句。

2. 第二个子句：递归检查更大的奇数因数

   • 首先验证D * D < N：若D的平方大于等于N，说明无需继续检查（因为N若有大于√N的因数，对应的另一个因数必然小于√N，之前已排查过），此子句失败。
   • 若D*D < N成立，计算D2 = D + 2（因已排除偶数因数，只需检查奇数），递归调用has_divisor(N, D2)，重复上述判断流程。

示例说明 #

• 判定is_prime(7)：
  调用\+ has_divisor(7,3)，第一个子句7 mod 3 = 1 ≠0失败；第二个子句3*3=9>7，条件不满足失败。has_divisor整体失败，\+取反后成功，判定7是素数。
• 判定is_prime(9)：
  调用\+ has_divisor(9,3)，第一个子句9 mod3=0直接成功，has_divisor整体成功，\+取反后失败，判定9不是素数。

内容的提问来源于stack exchange，提问作者chens11111010001