且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

在Prolog中计算数字是否为素数

更新时间:2023-02-11 16:22:47

参见 http://www.swi-prolog.org/pldoc/man?function=mod/2:

+IntExpr1 mod +IntExpr2
Modulo,定义为 Result = IntExpr1 - (IntExpr1 div IntExpr2) × IntExpr2,其中 div 为地板除法.

+IntExpr1 mod +IntExpr2
Modulo, defined as Result = IntExpr1 - (IntExpr1 div IntExpr2) × IntExpr2, where div is floored division.

所以R 应该是0.mod 只有一个结果.

So R should be 0. mod has only one result.

一个可行的解决方案是:

A working solution would be:

primeNumber(A) :-
    A > 1,                 % Negative numbers, 0 and 1 are not prime.
    prime_prime(A, 2).     % Begin iteration:

prime_prime(A, B) :-       % Test if A divides by B without remainder
    B >= A                 % The limit was reached?
    ->  true               %     Then it's prime.
    ;   0 is A mod B       % B divides A without a remainder?
    ->  false              %     Then it's not prime.
    ;   succ(B, C),        % Otherwise: C is B + 1
        prime_prime(A, C). % Test if C divides A.

顺便说一下,primeNumber/1(一个名为 primeNumber 的谓词,带有一个参数)是一个完全独立于 primeNumber/2 的谓词(同名,两个参数).只为起始值获取额外参数的子函数"通常具有相同的名称.因此,您应该使用 primeNumber 而不是 prime_prime,尽管在​​ Prolog 中您通常不使用驼峰式大小写.

By the way, primeNumber/1 (a predicate named primeNumber, with one argument) is a totally separate predicate from primeNumber/2 (same name, two arguments). A "subfunction" that only gets an extra argument for the start value, is usually given the same name. So instead of prime_prime you should just use primeNumber, though in Prolog you normally don't use camelCase.

使用 Sergei Lodyagin 在评论中提出的优化:

Using the optimization that Sergei Lodyagin proposed in the comments:

primeNumber(A) :-
    A > 1,                    % Negative numbers, 0 and 1 are not prime.
    sqrt(A, L),               % A prime factor of A is =< the square root of A.
    prime_prime(A, 2, L).     % Begin iteration:

prime_prime(A, B, L) :-       % Test if A divides by B without remainder
    B >= L                    % The limit was reached?
    ->  true                  %     Then it's prime.
    ;   0 is A mod B          % B divides A without a remainder?
    ->  false                 %     Then it's not prime.
    ;   succ(B, C),           % Otherwise: C is B + 1
        prime_prime(A, C, L). % Test if C divides A.

如果你使用预定义的谓词 between(+Low, +High, ?Value):

And if you use the predefined predicate between(+Low, +High, ?Value):

primeNumber(A) :-
    L is floor(sqrt(A)),
    \+ (between(2, L, X),
        0 is A mod X).

为了进一步减少迭代次数,您只需要测试奇数模块:

And to reduce the number of iterations even further, you only need to test for odd modules:

primeNumber(2).
primeNumber(A) :-
    A > 2,
    \+ 0 is A mod 2,
    L is floor(sqrt(A) / 2),
    \+ (between(1, L, X),
        0 is A mod (1 + 2*X)).