/* We need standard IO */
#include <stdio.h>

/* We need an integer square root */
#include "isqrt.c"

/* factor a number by Nahaj's method. */
/* Generating relation is N = pq = ss+r = (s-a)(s+a+2d) */
/*  DN wrt a = -(2(a+d)+1)                              */
/*  DN wrt d =   2(s-a)                                 */
main () {
  long n, p, q, x, d, a, s, t;

  printf ("Factor a positive odd number by Nahaj'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);
  x = 0; p = s; t = p*(p+2*x) - n;

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

  q = p+2*x;
  printf ("%ld*%ld=%ld\n",p,q,n);
}