/* We need standard IO */
**#include** <stdio.h>
/* Factor a NON-EVEN number by Fermat's method. */
/* Generating relation for this method is n = pq = (y-x)(y+x) */
/* Dn wrt X = -(2x+1) */
/* Dn wrt Y = 2y+1 */
main () {
long n, p, q, x, y, t;
printf ("Factor a positive odd number by Fermat'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;}
x = 0; y = 0; t = y*y - x*x - n;
while (t != 0) if (t<0) { t+=2*y+1; y ++; }
else { t-=2*x+1; x ++; }
q = y + x; p = y - x;
printf ("%ld*%ld=%ld\n", p, q, n);
}

# Go to ...

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