/* We need standard IO */
**#include** <stdio.h>
/* We need an integer square root */
**#include** "isqrt.c"
/* factor a number by Halleck's method. */
/* This version is straight from the defining relation */
/* Generating relation N = p*q = ss+r = (s-a)*(s+b) */
/* Dn wrt a = -(s+b) */
/* dn wrt b = s-a */
main () {
long n, p, q, a, b, s, t;
printf ("Factor a positive number by Halleck'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);
a = 0; b = 0; t = (s-a)*(s+b) - n;
while (t!=0) if (t<0) { t += s-a; b++; }
else { t -= s+b; a++; }
p = s-a; q = s+b;
printf ("%ld*%ld=%ld\n",p,q,n);
}

# Go to ...

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