#include <stdio.h> #include <string.h> long long gcd(long long a, long long b) { while (a != 0) { long long c = a; a = b%a; b = c; } return (b<0) ? -b : +b; } #define MAX 1000000 bool seen[MAX]; long long unseen = 1; long long unseenOdd = 1; #define WANTED 10001 long long a[WANTED]; long long u = 1; int main() { memset(seen, 0, sizeof(seen)); memset(a, 0, sizeof(a)); long long ppp = 1; long long pp = 1; long long p = 1; for (long long n=1; u<WANTED; n++) { bool found = false; long long x = ppp*pp*p; long long v; long long step; if (x%2==0) { v = unseenOdd; step = 2; } else { v = unseen; step = 1; } for (; v<MAX; v+=step) { if (!seen[v] && gcd(v, x)==1) { found = true; break; } } if (found) { if (v<WANTED) { a[v] = n; while (u < WANTED && a[u]) { printf("%lld %lld\n", u, a[u]); fflush(stdout); u++; } } seen[v] = true; while (unseen < MAX && seen[unseen]) { unseen++; } while (unseenOdd < MAX && seen[unseenOdd]) { unseenOdd+=2; } ppp = pp; pp = p; p = v; } else { break; } } return 0; }