#include <stdio.h>

struct Quoz {
  int numerator;
  int denominator;
};

void norm(struct Quoz *p) {
  int a, b, r;
  a = p->numerator;
  b = p->denominator;
  if (a < 0 && b >= 0) { a = -a; }
  if (a >= 0 && b < 0) { b = -b; }
  if (a < 0 && b < 0) { a = -a; b = -b; }
  for (;;) {
    r = a % b;
    if (r == 0)
      break;
    a = b;
    b = r;
  }
  p->numerator /= b;
  p->denominator /= b;
}

struct Quoz add(struct Quoz a, struct Quoz b) {
  struct Quoz c;
  c.numerator = b.denominator * a.numerator + b.numerator * a.denominator;
  c.denominator = a.denominator * b.denominator;
  norm(&c);
  return c;
}

struct Quoz mul(struct Quoz a, struct Quoz b) {
  struct Quoz c;
  c.numerator = a.numerator * b.numerator;
  c.denominator = a.denominator * b.denominator;
  norm(&c);
  return c;
}

struct Quoz div(struct Quoz a, struct Quoz b) {
  struct Quoz c;
  c.numerator = a.numerator * b.denominator;
  c.denominator = a.denominator * b.numerator;
  norm(&c);
  return c;
}

struct Quoz kmul(struct Quoz a, int n) {
  struct Quoz c;
  c.numerator = a.numerator * n;
  c.denominator = a.denominator;
  norm(&c);
  return c;
}

void set(struct Quoz *p, int a, int b) {
  p->numerator = a;
  p->denominator = b;
}

void put(struct Quoz n) {
  printf("(%d/%d)\n", n.numerator, n.denominator);
}

int rootZ(int x) {
  int i;
  for (i = 1;; i++) {
    if (i * i > x)
      break;
  }
  return i - 1;
}

int QuozZ(struct Quoz u) { return u.numerator / u.denominator; }

int isZero(struct Quoz u) {
  return (u.numerator == 0);
}

void f(int n) {
  struct Quoz a, b, c, d, t, r, y;
  int x, s;
  int i;

  x = n;
  set(&a, 1, 1);
  set(&b, 0, 1);

  for (i = 0; i < 20; i++) {
    /* (int)(a*root(x) + b) -> s */
    {
      int m;
      struct Quoz u, v, w;
      m = rootZ(x);
      u = a;
      v = kmul(u, m);
      w = add(v, b);
      s = QuozZ(w);
    }
    /* output s */
    if (i == 0) printf("%d; ", s); else printf("%d, ", s);

    /* b = b - s */
    set(&t, -s, 1);
    b = add(b, t);

    /* (c*root(x) + d) <- 1/(a*root(x) + b) */
    r = mul(a, a);
    r = kmul(r, x);
    y = mul(b, b);
    y = kmul(y, -1);
    r = add(r, y);

    if(isZero(r))
      break;

    c = div(a, r);
    d = div(b, r);
    d = kmul(d, -1);

    /* (a, b) <- (c, d) */
    a = c;
    b = d;
  }
  putchar('\n');
}

int main() {
  int n;
  for (n = 1; n <= 10; n++) {
    printf("%d: ", n);
    f(n);
  }
  return 0;
}
/* end */

1: 1; 
2: 1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
3: 1; 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 
4: 2; 
5: 2; 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
6: 2; 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 
7: 2; 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 
8: 2; 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 
9: 3; 
10: 3; 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,