CLPFD约束:是素数

Question

我甚至不确定这是否可能，但我正在尝试编写一个谓词prime/1，它将其参数限制为素数。

我遇到的问题是，我没有找到任何表达“将该约束应用于所有小于变量整数的整数”的方法。

下面是一次不起作用的尝试：

prime(N) :-
    N #> 1 #/\                       % Has to be strictly greater than 1
    (
        N #= 2                       % Can be 2
        #\/                          % Or
        (
            N #> 2 #/\               % A number strictly greater than 2
            N mod 2 #= 1 #/\         % which is odd
            K #< N #/\
            K #> 1 #/\
            (#\ (
                N mod K #= 0         % A non working attempt at expressing:
                                         “there is no 1 < K < N such that K divides N”
            ))
        )
    ).

我希望#\能够像\+一样运行，并检查它对于所有可能的情况都是错误的，但是情况似乎并非如此，因为这个实现是这样做的：

?- X #< 100, prime(X), indomain(X).
X = 2 ;    % Correct
X = 3 ;    % Correct
X = 5 ;    % Correct
X = 7 ;    % Correct
X = 9 ;    % Incorrect ; multiple of 3
X = 11 ;   % Correct
X = 13 ;   % Correct
X = 15     % Incorrect ; multiple of 5
…

基本上，这与2\/{Odd integers greater than 2}是统一的。

编辑

表示一个数字是而不是素数非常容易：

composite(N) :-
    I #>= J,
    J #> 1,
    N #= I*J.

基本上：“N是复合的，如果它可以用I >= J > 1编写为I*J”。

我仍然无法“否定”这些限制。我尝试过使用类似#==> (暗示)之类的东西，但这一点似乎根本就不是含意！N #= I*J #==> J #= 1将适用于复合数字，尽管12 = I*J并不意味着必然是J = 1！

Answer 1

prime/1

这花了我很长时间，我相信这远远不是很有效率，但这似乎是可行的，所以这里没有什么：

我们为约束这个例子创建一个自定义约束传播器(以下为prime/1 )，如下所示：

:- use_module(library(clpfd)).
:- multifile clpfd:run_propagator/2.

prime(N) :-
    clpfd:make_propagator(prime(N), Prop),
    clpfd:init_propagator(N, Prop),
    clpfd:trigger_once(Prop).

clpfd:run_propagator(prime(N), MState) :-
    (
        nonvar(N) -> clpfd:kill(MState), prime_decomposition(N, [_])
        ;
        clpfd:fd_get(N, ND, NL, NU, NPs),
        clpfd:cis_max(NL, n(2), NNL),
        clpfd:update_bounds(N, ND, NPs, NL, NU, NNL, NU)
    ).

如果N 是一个变量，则将其下界约束为2，或者如果它大于2，则保持它原来的下界。

如果N 是，那么我们使用prime_decomposition/2谓词检查N是否为素数：

prime_decomposition(2, [2]).
prime_decomposition(N, Z) :-
    N #> 0,
    indomain(N),
    SN is ceiling(sqrt(N)),
    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 -> !, false
        ;
        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 -> !, false
        ;
        D1 #= D+2,
        (    
            D1 #> SN ->
            LF = [N |L]
            ;
            prime_decomposition_2(N, SN, D1, L, LF)
        )
    ).

显然，您可以用任何确定性素数检查算法替换这个谓词。该算法是对素因式分解算法的一种修正，一旦找到一个因子，它就被修改为失败。

一些疑问

?- prime(X).
X in 2..sup,
prime(X).


?- X in -100..100, prime(X).
X in 2..100,
prime(X).


?- X in -100..0, prime(X). 
false.


?- X in 100..200, prime(X).
X in 100..200,
prime(X).


?- X #< 20, prime(X), indomain(X).
X = 2 ;
X = 3 ;
X = 5 ;
X = 7 ;
X = 11 ;
X = 13 ;
X = 17 ;
X = 19.

?- prime(X), prime(Y), [X, Y] ins 123456789..1234567890, Y-X #= 2, indomain(Y).
X = 123457127,
Y = 123457129 ;
X = 123457289,
Y = 123457291 ;
X = 123457967,
Y = 123457969
…


?- time((X in 123456787654321..1234567876543210, prime(X), indomain(X))).
% 113,041,584 inferences, 5.070 CPU in 5.063 seconds (100% CPU, 22296027 Lips)
X = 123456787654391 .

几个问题

这个约束的传播并不像它应该的那样强烈。例如：

?- prime(X), X in {2,3,8,16}.
X in 2..3\/8\/16,
prime(X).

当我们知道8和16是不可能的，因为它们是偶数。

我试图在传播者中添加其他约束，但他们似乎比任何其他限制都慢，所以我不确定我是否做错了什么，或者更新约束是否比标记时检查素数要慢。