hansdef.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                                    */
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=0; x=0; t = (q-2*x)*q - n;

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

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

Go to ...


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