Поиск основных факторов в Прологе - PullRequest
Новая
       42

Поиск основных факторов в Прологе

0 голосов
/ 02 марта 2019 
prime_factors(N, [_:_]) :- prime_factors(N, [_:_], 2).

prime_factors(N, [_:_], D) :- N mod D == 0,  N1 is N div D, 
                          prime_factors(N1, [_:D], D).

prime_factors(N, [_:_], D) :- N mod D =\= 0, D1 is D+1, prime_factors(N, [_:_], D1).

Это мое предлагаемое решение, чтобы найти основные факторы входных данных N.

Когда я пытаюсь запустить его, я получаю сообщение о том, что такой предикат / 2 не существует - это мой синтаксискак-то не так с расширенным предикатом / 3?

1 Ответ

0 голосов
/ 02 марта 2019

Использование второго параметра, который, по-видимому, унифицируется только во втором случае, не имеет особого смысла.Кроме того, это не способ, которым вы все равно строите список в Прологе, так как:

  1. "cons" имеет синтаксис [H|T], поэтому он должен быть [_|_];
  2. с помощью подчеркивания предикаты не интересуются значениями, вы каждый раз передаете другие параметры;и
  3. в Прологе, как правило, не создаются списки с ответами, обычно используется откат назад.Можно использовать findall/3, чтобы позже составить список.Обычно это лучше, поскольку это означает, что мы можем также запросить, например, prime_factor(1425, 3), чтобы проверить, является ли 3 главным фактором 1425.

Таким образом, мы можем построить предикат, который выглядит следующим образом:

prime_factor(N, D) :-
    find_prime_factor(N, 2, D).

find_prime_factor(N, D, D) :-
    0 is N mod D.
find_prime_factor(N, D, R) :-
    D < N,
    (0 is N mod D
    -> (N1 is N/D, find_prime_factor(N1, D, R))
    ;  (D1 is D + 1, find_prime_factor(N, D1, R))
    ).

Например: 

?- prime_factor(1425, R).
R = 3 ;
R = 5 ;
R = 5 ;
R = 19 ;
false.

?- prime_factor(1724, R).
R = 2 ;
R = 2 ;
R = 431 ;
false.

Если нам нужен список всех простых факторов, мы можем использовать findall/3 для этого: 

prime_factors(N, L) :-
    findall(D, prime_factor(N, D), L).

Дляпример: 

?- prime_factors(1425, R).
R = [3, 5, 5, 19].

?- prime_factors(1724, R).
R = [2, 2, 431].

?- prime_factors(14, R).
R = [2, 7].

?- prime_factors(13, R).
R = [13].
...