Prolog程序检查数字是否为Prime

Question

我根据逻辑来编写以下程序,素数只能被1和它自身整除.所以我只是经历了将它划分为大于1且小于其自身的所有数字的过程,但我似乎遇到了问题,因为我将所有输入的数字都设为真.这是我的代码......

divisible(X,Y) :-
    Y < X,
    X mod Y is 0,
    Y1 is Y+1,
    divisible(X,Y1).

isprime(X) :-
    integer(X),
    X > 1,
    \+ divisible(X,2).

提前致谢 :)

Answer 1

我是Prolog的初学者,但设法解决了你的问题.

divisible(X,Y) :- 0 is X mod Y, !.

divisible(X,Y) :- X > Y+1, divisible(X, Y+1).

isPrime(2) :- true,!.
isPrime(X) :- X < 2,!,false.
isPrime(X) :- not(divisible(X, 2)).

主要问题是声明X mod Y is 0.谓词is有两个(左和右)参数,但左参数必须是一个常量或变量,它在谓词执行时已经统一.我只是交换了这些值.其余代码用于检查数字2(这是素数)和数字少于2(不是素数)

我忘了提到比较Y < X是错误的,因为你想测试2和X-1之间的所有数字,那个比较包括X.

Answer 2

这个答案是@ lefunction之前回答的后续内容.

isPrime2/1尽可能接近isPrime1/1几个关键变化(下面突出显示):

isPrime2(2) :-
    !.
isPrime2(3) :-
    !.
isPrime2(X) :-
    X > 3,
    X mod 2 =\= 0,
    isPrime2_(X, 3).

isPrime2_(X, N) :-
    (  N*N > X
    -> true
    ;  X mod N =\= 0,
       M is N + 2,
       isPrime2_(X, M)
    ).
    

我们来查询!

?- time(isPrime1(99999989)).
% 24,999,999 inferences, 3.900 CPU in 3.948 seconds (99% CPU, 6410011 Lips)
true.

?- time(isPrime2(99999989)).
% 5,003 inferences, 0.001 CPU in 0.001 seconds (89% CPU, 6447165 Lips)
true.