#include <stdio.h>
#include <stdlib.h>

struct abr {
  long label;
  struct abr *g;
  struct abr *d;
};

typedef struct abr abr;

abr *singleton_abr(long x) {
  abr *r = (abr *) malloc(sizeof(abr));
  if (r != NULL) {
    r->d = NULL;
    r->g = NULL;
    r->label = x;
  }
  return r;
}

abr *add(abr *r, long x) {
  abr *i = r;
  if (i == NULL)
    return singleton_abr(x);
  
  while(i->label != x) {
    if (i->label < x) {
      if (i->d == NULL)
	i->d=singleton_abr(x);
      i = i->d;
    }
    else {
      if (i->g == NULL)
	i->g = singleton_abr(x);
      i = i->g;
    }
  }
  return i;
}

abr *array_to_tree(long *t, long n) {
  abr *r = singleton_abr(t[0]);
  long i = 0;
  for(i=1;i<n;i++)
    add(r, t[i]);
  return r;
}

abr *search(abr *r, long x) {
  abr *i = r;
  while(i != NULL) {
    if (i->label == x)
      return i;
    if (i->label < x)
      i = i->d;
    else
      i = i->g;
  }
  return NULL;
}

long min(abr *r) {
  abr *i = r;
  if (i == NULL)
    return 0;
  
  while(i->g != NULL) {
    i = i->g;
  }
  return i->label;
}

long max(abr *r) {
  abr *i = r;
  if (i == NULL)
    return 0;
  
  while(i->d != NULL) {
    i = i->d;
  }
  return i->label;
}

abr *remove_node(abr *r, long x) {
  // On cherche x et son pere, c : 0 si x est le fils gauche de p, 1 sinon.
  abr *n = r;
  abr *p = NULL;
  long c = 0;

  while(n!=NULL && n->label != x) {
    if (n->label < x) {
      if (n->d->label == x) {
	p=n;
	c=1;
      }
      n = n->d;
    }
    else {
      if (n->g->label == x) {
	p=n;
	c=0;
      }
      n = n->g;
    }
  }

  // On n'a pas trouvé x
  if (n == NULL) return r;

  // n est une feuille
  if (n->d == NULL && n->g == NULL) {
      free(n);
      if (p != NULL) {
	if (c == 0) p->g = NULL;
	else p->d = NULL;
	return r;
      }
      return NULL; // x est une feuille et la racine ... on a vidé l'arbre
  }

  // n est de degré 1
  if (n->d == NULL) {
    if (c == 0) p->g = n->g;
    else p->d = n->g;
    free(n);
    return r;
  }

  if (n->g == NULL) {
    if (c == 0) p->g = n->d;
    else p->d = n->d;
    free(n);
    return r;
  }

  // Sinon n a deux fils. On remplace sa valeur par le minimum du fils droit
  long m = min(n->d);
  n->label = m;

  // On sait que le minimum m est de degré au plus 1
  remove_node(n->d, m);
  return r;
}


void print_tree(abr *r) {
  if (r!=NULL) {
    print_tree(r->g);
    printf("%d\n", r->label);
    print_tree(r->d);
  }
}

void free_tree(abr *r) {
  if (r != NULL) {
    free_tree(r->g);
    free_tree(r->d);
    free(r);
  }
}

void segment(abr *r, long a, long b) {
  if (a == b)
    add(r, a);
  else {
    long m=(a+b)/2;
    add(r, m);
    segment(r, a, m);
    segment(r, m+1, b);
  }
}

abr *crible(long n) {
  abr *r = singleton_abr(n/2);
  segment(r, 0, n);

  long i, j;
  for(i=2;i<n;i++) {
    j = 2;
    while(j*i <= n) {
      remove_node(r, i*j);
      j++;
    }
  }
  return r;
}

long main() {
  abr *c = crible(100000);
  long  n = 1487932939581322413763429;
  printf("%d\n", n);
  free_tree(c);
  
  return 0;
}