/* 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 */
main () {
long n, p, q, x, q2, x2, 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=0; x=0; q2=2*q; x2=2*x; t = (q-x2)*q - n;
while (t!=0) if (t<0) { t += q2-x2+1; q2 += 2;}
else { t -= q2; x2 += 2;}
q = q2 / 2; p = q - x2;
printf ("%ld*%ld=%ld\n",p,q,n);
}

# Go to ...

This page is http://www.cc.utah.edu/~nahaj/factoring/hans.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on December 24th, 2013