# leroydef.c:

```/* We need standard IO */
#include <stdio.h>

/* We need an integer square root */
#include "isqrt.c"

/* factor a number by LeRoy's method.                   */
/*  This version is straight from the defining relation */
/* Note that an appropriate S exists, within 1 of the square root */
/* Generating relation N = ss+r = (s-2*a)*(s+2*b)       */
/*  Dn wrt a = -2*(s+2*b)                               */
/*  dn wrt b =  2*(s-2*a)                               */
main () {
long n, p, q, a, b, s, t;

printf ("Factor a positive odd number by LeRoy's method\n");
printf ("N = \n"); scanf ("%ld", &n);
printf ("Factoring %ld\n", n);
if (n<1) { printf ("N must be greater than zero\n"); return 1;}
if (n%2 == 0) { printf ("N must be odd\n"); return 2;}

s = isqrt(n); t = s*s-n;
if (t==0) {printf ("%ld*%ld=%ld\n", s, s, n); return s;}

if (s%2 != 1) s++;

a = 0; b = 0; t = (s-2*a)*(s+2*b) - n;

while (t!=0) if (t<0) { t += 2*(s-2*a); b++; }
else     { t -= 2*(s+2*b); a++; }

p = s-2*a; q = s+2*b;
printf ("%ld*%ld=%ld\n",p,q,n);
}
```

# Go to ...

```This page is http://www.cc.utah.edu/~nahaj/factoring/leroydef.c.html