// program directly inspired by A247665 #include <stdio.h> #include <string.h> #define MAX (1LL<<29) // requires ~ 9Gb bool *sieve = 0; // prime sieve long long *gpf = 0; // greatest prime factor long long *sf = 0; // selection sieve (0 = available) long long *a = 0; // A354790 int main() { sieve = new bool[MAX]; gpf = new long long[MAX]; sf = new long long[MAX]; a = new long long[MAX]; memset(sieve, 0, MAX*sizeof(*sieve)); memset(gpf, 0, MAX*sizeof(*gpf)); memset(sf, 0, MAX*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; long long k=0; for (long long n=1;; n++) { while (sf[v]) { v++; if (v==MAX) { return 0; } } a[n]=v; if (gpf[v]!=v) { printf("%lld %lld\n", ++k, n); 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; }