#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100000 int *tab = 0; int pc = 0; int *first = 0; int lastpi = 0; int unseen = 1; int other(int v) { first[lastpi] = tab[v]; tab[v] = 0; while (unseen < MAX && tab[unseen]==0) { unseen++; } int best = MAX; int bestpi = 0; for (int pi=1; pi <= lastpi+1 && pi <= pc; pi++) { if (first[pi] < best) { best = first[pi]; bestpi = pi; } } if (best<MAX) { lastpi = bestpi; return best; } else { fprintf(stderr, "the end\n"); exit(0); } } int main() { tab = (int*) malloc(MAX * sizeof(int)); if (tab==0) { fprintf(stderr, "out of memory\n"); exit(1); } memset(tab, 0, MAX * sizeof(int)); for (int n=2; n<MAX; n++) { if (!tab[n]) { pc++; for (int m=n; m<MAX; m+=n) { tab[m] = 1; } } } fprintf(stderr, "got %d primes up to %d\n", pc, MAX); first = (int*) malloc((1+pc) * sizeof(int)); if (first==0) { fprintf(stderr, "out of memory\n"); exit(1); } memset(tab, 0, MAX * sizeof(int)); memset(first, 0, (1+pc) * sizeof(int)); int pi = 0; for (int n=2; n<MAX; n++) { if (!tab[n]) { pi++; first[pi] = n; int p = n; for (int m=2*n; m<MAX; m+=n) { if (!tab[m]) { tab[p] = m; p = m; } } tab[p] = MAX; } } int v = 1; for (int n=1; n<=10000; n++) { printf("%d %d\n", n, v); fflush(stdout); v = other(v); } free(tab); return 0; }