// program directly inspired by A247665 #include <stdio.h> #include <string.h> #define MAX 105000 bool sieve[MAX]; // prime sieve long long gpf [MAX]; // greatest prime factor long long sf [MAX]; // selection sieve (0 = available) long long a [MAX]; // A354790 int main() { memset(sieve, 0, sizeof(sieve)); memset(gpf, 0, sizeof(gpf)); memset(sf, 0, sizeof(sf)); for (long long n=2; n<MAX; n++) { if (!sieve[n]) { for (long long m=n; m<MAX; m+=n) { sieve[m] = true; gpf[m] = n; } // mark non-squarefree numbers long long n2 = n*n; for (long long s=n2; s<MAX; s+=n2) { sf[s]++; } } } long long v=1; for (long long n=1;; n++) { while (sf[v]) { v++; if (v==MAX) { return 0; } } printf("%lld %lld\n", n, a[n]=v); fflush(stdout); sf[v]++; // mark out numbers not coprime to v long long r=v; while (r>1) { long long g=gpf[r]; r/=g; for (long long m=g; m<MAX; m+=g) { sf[m]++; } } if (n%2==0) { long long r=a[n/2]; while (r>1) { long long g=gpf[r]; r/=g; for (long long m=g; m<MAX; m+=g) { sf[m]--; if (sf[m]==0 && v>m) { v=m; } } } } } return 0; }