/* We need standard IO */
**#include** <stdio.h>
**#include** "isqrt.c"
/* factor a number by John's method. */
/* Generating relation is N = q*p */
/* DN wrt q = p */
/* DN wrt p = q */
/* They don't differ in sign, so we have to run one negative,
* Since we know p is less than the square root, we'll run it
* down from there, and q up from there.
*/
main () {
long n, p, q, t;
printf ("Factor a positive number by John'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;}
q=isqrt(n); p = q; t = p*q - n;
while (t!=0) {
if (t<0) { t += p; q++;}
else { t -= q; p--;}
} ;
printf ("%ld*%ld=%ld\n",p,q,n);
}

# Go to ...

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