#include <stdio.h> #include <stdlib.h> int gcd(int a, int b) { while (a != 0) { int c = a; a = b%a; b = c; } return (b<0) ? -b : +b; } #define MAX 1000000 int rad[MAX]; // A007947, 0 means already used int unseen = 1; #define K 3 int rrr[K]; int other() { int forbidden = rrr[0]; for (int k=1; k<K; k++) { forbidden = gcd(forbidden, rrr[k]); } int mandatory = rrr[K-1] / gcd(forbidden, rrr[K-1]); for (int v=mandatory*(unseen/mandatory); v<MAX; v+=mandatory) { if (rad[v] && gcd(forbidden, v)==1) { for (int k=1; k<K; k++) { rrr[k-1] = rrr[k]; } rrr[K-1] = rad[v]; rad[v] = 0; // using v while (unseen<MAX && rad[unseen]==0) { unseen++; } return v; } } exit(0); } int main() { for (int n=1; n<MAX; n++) { rad[n] = 1; } for (int n=2; n<MAX; n++) { if (rad[n]==1) { // n is prime for (int m=n; m<MAX; m+=n) { rad[m] *= n; } } if (rad[n]<n) { // n is not squarefree - we ignore it rad[n] = 0; } } rad[0] = 0; // avoid 0 for (int n=0; n<K; n++) { rrr[n] = 1; } for (int n=1; n<=10000; n++) { printf("%d %d\n", n, other()); fflush(stdout); } return 0; }