#include <bitset> #include <iostream> #include <map> #include <string.h> #include <vector> using namespace std; #define MAX (1LL<<30) #define SMALL (1LL<<35) class Arit { public: Arit(long long n, long long v) : _min(n), _mod(v), _max(n+(v-1)*v) {} bool contains(long long v) { if (v>=_min && v<=_max && (v-_min)%_mod==0) { return true; } else { return false; } } private: const long long _min; const long long _mod; const long long _max; }; bitset<SMALL> *small = 0; vector<Arit*> big; bool test(long long n) { if (n<SMALL) { return small->test(n); } else { for (size_t i=0; i<big.size(); i++) { if (big[i]->contains(n)) { return true; } } return false; } } map<long,bool> seen; #define WANTED 5001LL long long a[WANTED]; void set(long long n, long long v) { long long min = n; long long max = n + (v-1)*v; seen[v] = true; for (long long n=min; n<=max && n<SMALL; n+=v) { small->set(n); if (n<WANTED) { a[n] = v; } } if (max>=SMALL) { big.push_back(new Arit(n, v)); } } int main() { small = new bitset<SMALL>; memset(a, 0, sizeof(a)); for (long long n=1; n<MAX; n++) { if (a[n]==0) { for (long long v=1; v<MAX; v++) { if (!seen.count(v)) { bool ok = true; long long m = n; for (long long k=v; k>0; k--) { if (test(m)) { ok = false; break; } m += v; } if (ok) { set(n, v); break; } } } } if (a[n]==0) { break; } else { cout << n << ' ' << a[n] << endl; } } delete small; small = 0; for (size_t i=0; i<big.size(); i++) { delete big[i]; } big.clear(); return 0; }