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 和 I >= J > 1”。

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

Answer 1

`prime/1`

这花了我很长一段时间，我确信它远非高效，但这似乎有效，所以这里什么也没有：

我们为约束 prime/1 创建一个自定义约束传播器（在 this example 之后），因此：

:- 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，如果大于[则保持其原始下界=17=].

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

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 是不可能的，因为它们是偶数。

我试图在传播器中添加其他约束，但它们似乎比其他任何东西都更能减慢它的速度，所以我不确定我是否做错了什么，或者更新约束是否比检查更慢标记时的素数。

CLPFD约束：是质数

CLPFD constraint: is a prime number

primes

prolog

swi-prolog

clpfd

编辑

`prime/1`

一些查询

一些问题