#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 2000000000ll bool *sieve = 0; unsigned char *xdiv = 0; long long seen[256]; int unseen = 0; int main() { sieve = (bool*)malloc(MAX*sizeof(*sieve)); xdiv = (unsigned char*)malloc(MAX*sizeof(*xdiv)); if (sieve==0 || xdiv==0) { fprintf(stderr, "# out of memory"); exit(1); } memset(sieve, 0, MAX*sizeof(*sieve)); memset(xdiv, 0, MAX*sizeof(*xdiv)); memset(seen, 0, sizeof(seen)); sieve[1] = true; long long pi = 0; for (long long n=1; n<MAX; n++) { if (!sieve[n]) { pi++; for (long long m=n; m<MAX; m+=n) { sieve[m] = true; if (m%pi==0) { xdiv[m]++; } } } if (!seen[xdiv[n]]) { seen[xdiv[n]] = n; while (seen[unseen]) { printf("%d %lld\n", unseen, seen[unseen]); fflush(stdout); unseen++; } } } return 0; }