/* We need standard IO */
**#include** <stdio.h>
**#include** "isqrt.c"
/* factor a number by Anon's method. Generating relation that */
/* generated this was N = 2*y*p - p*p */
/* d wrt p = 2*y-2*p-1 = 2*(y-p) -1 */
/* d wrt y = 2p */
/* Since we know p is less than y, both are positive, so we have
* to run one of the variables negative... We'll pick p
* (and we know p is at least as small as the square root, and
* y is at least as large as it.)
* d wrt -p = - 2*y + 2*p -1 = -2(y-p)-1
*/
main () {
long n, p, q, y, s, t;
printf ("Factor a positive odd number by anon'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 not be even.\n"); return 2;}
s = isqrt (n);
p = s; y = 0; t = 2*y*p - p*p - n;
while (t!=0) if (t<0) { t += p+p ; y++; }
else { t += p+p - y-y - 1; p--; }
q = 2*y-p;
printf ("%ld*%ld=%ld\n",p,q,n);
}

# Go to ...

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