Prime decomposition: Difference between revisions

=={{header|Prolog}}==

<lang 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)

)

).</lang>

OutPut :

<lang Prolog> ?- time(prime_decomp(9007199254740991, L)).

% 138,882 inferences, 0.344 CPU in 0.357 seconds (96% CPU, 404020 Lips)

L = [20394401,69431,6361].

?- time(prime_decomp(576460752303423487, L)).

% 3,579,642 inferences, 68.719 CPU in 70.161 seconds (98% CPU, 52091 Lips)

L = [3203431780337,179951].

</lang>