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