# finnish.c:

```/* We need an integer square root. */
#include "isqrt.c"
/* We need standard IO */
#include <stdio.h>

/* Factor a NON-EVEN number by Mika's method. */
/* Generating relation for this method is 0 = XX - D*D - 2*S*D + R */
/*  Dn wrt X = 2X+1                                                */
/*  Dn wrt D = -2(d+s)-1  (which is -2Y-1 from Fermat's method)    */
/* computation of final factors uses x = a+d, and p=(s-a), q=(s+a+2d) */
main () {
long n, p, q, x, d, s, r, t, a;

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

s = isqrt(n); r = n - s*s;
x = 0; d = 0; t = x*x - d*d - 2*s*d + r - 0;

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

a = x - d;
q = s + a + 2*d; p = s - a;
printf ("%ld*%ld=%ld\n", p, q, n);
}
```

# Go to ...

```This page is http://www.cc.utah.edu/~nahaj/factoring/finnish.c.html