38 lines
794 B
Prolog
38 lines
794 B
Prolog
prime_decomp(N, L) :-
|
|
SN is sqrt(N),
|
|
prime_decomp_1(N, SN, 2, [], L).
|
|
|
|
|
|
prime_decomp_1(1, _, _, L, L) :- !.
|
|
|
|
% Special case for 2, increment 1
|
|
prime_decomp_1(N, SN, D, L, LF) :-
|
|
( 0 is N mod D ->
|
|
Q is N / D,
|
|
SQ is sqrt(Q),
|
|
prime_decomp_1(Q, SQ, D, [D |L], LF)
|
|
;
|
|
D1 is D+1,
|
|
( D1 > SN ->
|
|
LF = [N |L]
|
|
;
|
|
prime_decomp_2(N, SN, D1, L, LF)
|
|
)
|
|
).
|
|
|
|
% General case, increment 2
|
|
prime_decomp_2(1, _, _, L, L) :- !.
|
|
|
|
prime_decomp_2(N, SN, D, L, LF) :-
|
|
( 0 is N mod D ->
|
|
Q is N / D,
|
|
SQ is sqrt(Q),
|
|
prime_decomp_2(Q, SQ, D, [D |L], LF);
|
|
D1 is D+2,
|
|
( D1 > SN ->
|
|
LF = [N |L]
|
|
;
|
|
prime_decomp_2(N, SN, D1, L, LF)
|
|
)
|
|
).
|