/* 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);
}