#include <algorithm> #include <cmath> #include <iostream> #include <stdlib.h> #include <string.h> using namespace std; void move(long long &x, long long &y) { long long w = max(abs(x), abs(y)); if (y==-w) { x++; } else if (x==-w) { y--; } else if (y==w) { x--; } else { y++; } } inline long long square(long long v) { return v*v; } long long index(long long x, long long y) { if (x>abs(y)) { return 1 + square(2*x-1) + (x+y-1); } else if (x>y) { return 1 + 2*-y*(1-2*y) + (x-y); } else if (y>=abs(x)) { return 1 + 2*y*(2*y-1) + (y-x); } else { return 1 + 4*square(x) + (-y-x); } } #define MAX (1LL<<33) bool *sieve = 0; bool is(long long x, long long y, long long w2) { long long dx = 0; long long dy = 0; for (long long s=w2; s>0; s--) { long long k = index(x+dx, y+dy); if (k>=MAX) { exit(0); } else if (!sieve[k]) { return false; } move(dx, dy); } return true; } int main() { sieve = new bool[MAX]; memset(sieve, 0, MAX*sizeof(*sieve)); sieve[1] = true; // 1 is not prime for (long long n=2; n<MAX; n++) { if (!sieve[n]) { for (long long m=2*n; m<MAX; m+=n) { sieve[m] = true; } } } long long x=0; long long y=0; long long w=0; long long w2=square(1+2*w); for (long long n=1; n<MAX; n++) { while (is(x, y, w2)) { cout << w << ' ' << n << endl; w++; w2=square(1+2*w); } move(x, y); } delete[] sieve; return 0; }