#include <iostream> #include <string.h> #define MAX 100000000 using namespace std; long long prod[MAX]; #define WANTED 10001 long long a[WANTED]; int u = 1; long long min(long long t, long long u) { if (t<u) { return t; } else { return u; } } int main() { memset(prod, 0, sizeof(prod)); memset(a, 0, sizeof(a)); int v = 1; int k = 0; long long pp = -1; for (long long n=1; n<=1000000000000000000ll; n++) { for (int o=1;; o++) { int ov = o*v; if (ov>=MAX) { cerr << "# the end" << endl; return 1; } int old = prod[ov]; if (old+1<=ov) { if (ov<WANTED) { if (!old) { a[ov] = min(o, v); } else { a[ov] = min(a[ov], min(o, v)); } } v=o; if (pp==ov) { // giant step - the sequence is 2-periodic for a while if ((ov-old)%2==0) { v = ov/o; } prod[ov] = ov; n += ov-old-1; } else { prod[ov] = old+1; pp = ov; } while (prod[u]==u) { printf("%d %lld\n", u, a[u]); fflush(stdout); u++; if (u==WANTED) { return 0; } } break; } } } return 0; }