Facteurs d'un nombre

Question

Donc, je suis relativement nouveau à Prolog, et bien que ce problème soit facile dans de nombreuses autres langues, j'ai beaucoup de problèmes avec cela. Je veux générer une liste de facteurs pour un certain nombre N. Je l'ai déjà construit un prédicat qui me dit si un nombre est un facteur:

% A divides B 
% A is a factor of B 
divides(A,B) :- A =\= 0, (B mod A) =:= 0. 

% special case where 1 // 2 would be 0 
factors(1,[1]) :- !. 

% general case 
factors(N,L):- N > 0, factor_list(1, N, L). 
factor_list(S,E,L) :- S =< E // 2, f_list(S,E,L). 

f_list(S,E,[]) :- S > E // 2, !. 
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T). 
f_list(S,E,L)  :- S1 is S+1, f_list(S1,E,L). 

Toute aide serait appréciée.

EDIT

je assez bien changé ma solution complète, mais pour certains prédicats raison comme factors(9, [1]) retour vrai, quand je veux seulement revenir factors(9, [1,3]) vrai. Des pensées?

Answer 1

Voici pourquoi factors(9,[1]) est vrai: le moment de instanciations tentatives (c'est-à-dire, unifications) est éteint:

f_list(S,E,[]) :- S > E // 2, !. 
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T). 
f_list(S,E,L)  :- S1 is S+1, f_list(S1,E,L). 

%% flist(1,9,[1]) -> (2nd clause) divides(1,9), S1 is 2, f_list(2,9,[]). 
%% flist(2,9,[]) -> (3rd clause) S1 is 3, f_list(3,9,[]). 
%% ... 
%% flist(5,9,[]) -> (1st clause) 5 > 9 // 2, !. 

parce que vous pré-spécifier [1], lorsqu'il atteint 3 la queue est [] et la correspondre à la 2ème clause est empêché par ceci, bien que réussisse réussir en raison de divides/2.

La solution est de déplacer les unifications de la tête de clauses dans le corps, et les rendre seulement au bon moment, au plus tôt:

f_list(S,E,L) :- S > E // 2, !, L=[]. 
f_list(S,E,L) :- divides(S,E), !, L=[S|T], S1 is S+1, f_list(S1, E, T). 
f_list(S,E,L) :- S1 is S+1, f_list(S1,E,L). 

ci-dessus est habituellement écrit avec le if-else construction :

f_list(S,E,L) :- 
    (S > E // 2 -> L=[] 
    ; divides(S,E) -> L=[S|T], S1 is S+1, f_list(S1, E, T) 
    ;       S1 is S+1, f_list(S1, E, L) 
). 

vous pouvez également simplifier le prédicat principal comme

%% is not defined for N =< 0 
factors(N,L):- 
    ( N =:= 1 -> L=[1] 
    ; N >= 2 -> f_list(1,N,L) 
). 

Answer 2

P Personnellement, j'utilise une solution un peu plus simple:

factors(1,[1]):- true, !. 
factors(X,[Factor1|T]):- X > 0, 
between(2,X,Factor1), 
NewX is X // Factor1, (X mod Factor1) =:= 0, 
factors(NewX,T), !. 

Celui-ci accepte seulement une liste ordonnée des facteurs.

Answer 3

Voici une procédure simple basée sur l'énumération.

factors(M, [1 | L]):- factors(M, 2, L). 
factors(M, X, L):- 
    residue(M, X, M1), 
    ((M==M1, L=L1); (M1 < M, L=[X|L1])), 
    ((M1=1, L1=[]); (M1 > X, X1 is X+1, factors(M1, X1, L1))). 

residue(M, X, M1):- 
    ((M < X, M1=M); 
    (M >=X, MX is M mod X, 
    (MX=0, MM is M/X, residue(MM, X, M1); 
     MX > 0, M1=M))).