Factoring by Fermat's Method
predicates
factors(integer,integer,integer)
factors_1(integer,integer,integer,integer,integer)
floor(real,integer)
clauses
/* factors(N, F, G) is true if N is an odd integer greater than 1, F is */
/* the largest factor of N less than or equal to sqrt(N), and G = N / F. */
factors(N, F, G):-
N > 1,
1 = N mod 2,
S0 = sqrt(N),
floor(S0, S),
X = 2 * S + 1,
R = N - S * S,
factors_1(R, X, 1, F, G).
factors_1(0, X, Y, F, G):-
!,
F = (X - Y) div 2,
G = (X - 1) div 2 + (Y - 1) div 2.
factors_1(R, X, Y, F, G):-
R > 0, !,
R1 = R - X,
X1 = X + 2,
factors_1(R1, X1, Y, F, G).
factors_1(R, X, Y, F, G):-
R1 = R + Y,
Y1 = Y + 2,
factors_1(R1, X, Y1, F, G).
/* floor(R, I) is true if I is the largest integer not greater than the */
/* positive number R. */
floor(R, I):-R >= 0, I = R - 0.5.
Turbo Prolog Index
Home Page