在 Prolog 中查找梅森数

Question

我想在 Prolog 中找到前 10 个梅森素数，我已经实现了以下内容：

% Define a predicate to check if a number is prime.
is_prime(N) :-
    N > 1,
    \+ has_divisor(N, 2).

% Define a predicate to check if N has a divisor other than 1 and itself.
has_divisor(N, D) :-
    D =< sqrt(N),
    0 is N mod D,
    D > 1,
    !.

% Define a predicate to check if a number is a Mersenne prime.
is_mersenne_prime(P) :-
    is_prime(P),
    Mersenne is 2^P - 1,
    is_prime(Mersenne).

% Find the first 10 Mersenne prime numbers.
find_mersenne_primes(N, Count) :-
    Count > 0,
    is_mersenne_prime(N),
    write(N), write(' 2^'), write(N), write('-1'), nl,
    NewCount is Count - 1,
    NewN is N + 1,
    find_mersenne_primes(NewN, NewCount).
    
find_mersenne_primes(_, 0).

main :-
    write('Calculating the first 10 Mersenne prime numbers:'), nl,
    find_mersenne_primes(2, 10).

% Start the program when the Prolog file is consulted.
:- initialization(main).

我已经在 SWI Prolog 便携式中运行它，但出现以下错误：

% d:path compiled 0.00 sec, 7 clauses
Calculating the first 10 Mersenne prime numbers:
2 2^2-1
3 2^3-1
Warning: d:35: Initialization goal failed

prime 函数工作正常，但我对 find_Mersenne 函数有疑问，如何才能打印前 10 个素数评估数字？

谢谢

Answer 1

您需要同时修复

is_prime/1

和

find_mersenne_primes/2

。 对于前者，您可以采用 Prolog 转换，例如，您可以在关于素性测试的维基百科页面中找到代码。

is_prime(N):-
    N =< 3,
    N > 1, !.
is_prime(N):-
    (0 is N mod 2 ; 0 is N mod 3), !,
    false.
is_prime(N):-
    L is sqrt(N),
    is_prime_loop(N, 5, L+1), !.
is_prime_loop(N, I, Max):-
    I < Max,
    (   (0 is N mod I ; 0 is N mod I+2) ->  
        !, false ;
    is_prime_loop(N, I+6, Max)).
is_prime_loop(_, I, Max):-
    I >= Max, !.

那么你还需要

find_mersenne_primes(N, Count) :-
    Count > 0,
    NewN is N + 1,
    find_mersenne_primes(NewN, Count).
find_mersenne_primes(_, 0) :- !.

在第一个

find_mersenne_primes/2

子句下方。