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

/* factor a number by John's method. */
/* Generating relation is N = q*p    */
/*  DN wrt q = p                     */
/*  DN wrt p = q                     */
/* They don't differ in sign, so we have to run one negative,
 * Since we know p is less than the square root, we'll run it
 * down from there, and q up from there.
 */
main () {
  long n, p, q, t;

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

  q=isqrt(n); p = q; t = p*q - n;

  while (t!=0) {
     if (t<0) { t += p; q++;}
     else     { t -= q; p--;}
  } ;

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