bill.c:

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

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

/* factor a number by Bill's method.           */
/* Generating relation: N = p*q = (s-a)(s+a+c) */
/*   DN wrt a = -(2a+c+1)                      */
/*   DN wrt c =   s-a                          */
main () {
  long n, p, q, c, a, s, t;

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

  s = isqrt(n);
  c = 0; a = 0; t = (s-a)*(s+a+c) - n;

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

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

Go to ...

isqrt.c

This page is http://www.cc.utah.edu/~nahaj/factoring/bill.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on January 12th, 2009
And the underlying file was last modified on December 12th, 2005