#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 50000000 int *tau = 0; bool *is = 0; int f(int n) { for (int k=0; n<MAX; k++, n+=tau[n]) { if (is[n]) { return k; } } return -1; // the end } int main() { tau = (int*) malloc(MAX * sizeof(*tau)); is = (bool*) malloc(MAX * sizeof(*is)); if (!tau || !is) { fprintf(stderr, "# out of memory\n"); return 1; } memset(tau, 0, MAX * sizeof(*tau)); memset(is, 0, MAX * sizeof(*is)); for (int n=1; n<MAX; n++) { for (int m=n; m<MAX; m+=n) { tau[m]++; } } int w = 1; while (w<MAX) { is[w] = true; w += tau[w]; } int k = 0; int mx = -1; for (int n=1; n<MAX; n++) { int v = f(n); if (v<0) { break; // the end } if (mx < v) { mx = v; printf("%d %d\n", ++k, mx); fflush(stdout); } } free(tau); free(is); return 0; }