# hansfast.c:

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

/* factor a number by Han's method. */
/* Generating relation is N = pq = ss+r = (q-2x)q = qq-2xq */
/*  DN wrt x = -2q                                         */
/*  DN wrt q = 2(q-x)+1  = 2q-2x+1                         */
/*  DN2 wrt q = 4q+4-4x  = 4(q-x+1)                        */
/* (And observing that q must be odd)                      */
/* (And factoring out the factor of two in both branches)  */
main () {
long n, p, q, x, t;

printf ("Factor a positive odd number by Han'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 1;}

q=1; x=0; t = (q*q-2*x*q -n)/2;

while (t!=0) if (t<0) { t += 2*(q-x+1); q+=2; }
else     { t -= q;         x+=1; }

p = q - 2*x;
printf ("%ld*%ld=%ld\n",p,q,n);
}
```

# Go to ...

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