#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 15000000 int valuation(int n, int p) { int v = 0; while (n%p==0) { n /= p; v++; } return v; } int mask[MAX]; // masks of prime exponents bool seen[MAX]; // seen ? void init() { memset(mask, 0, sizeof(mask)); memset(seen, 0, sizeof(seen)); for (int n=2; n<MAX; n++) { if (!mask[n]) { // n is prime ! for (int m=n; m<MAX; m+=n) { mask[m] |= 1 << valuation(m,n); } } } } int unseen = 1; int other(int p) { seen[p] = true; while (seen[unseen] && unseen!=MAX) { unseen++; } for (int v=unseen; v<MAX; v++) { if (!seen[v] && (mask[p] & mask[v])==0) { return v; } } fprintf(stderr, "the end\n"); exit(1); } int main() { init(); int v = 1; for (int n=1; n<=10000; n++) { printf("%d %d\n", n, v); fflush(stdout); v = other(v); } return 0; }