ICPC 国内予選2013D 素数洞穴 AOJ 1189

解法：
大きめにとった二次元配列に1から10^6までの数の洞穴を書く。（たぶんここが一番めんどくさい
エラトステネスで素数をすぐ求められる配列を作っておく。
あとは最初に指定された位置から簡単なDPを解くだけ。（もはやDPと呼べるレベルではない気がするが、、、

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int m[1600][1600];
int dp[1600][1600][2];
bool prime[1000010];

int main(){
    int a = 800,b = 800;
    int dir; //今向いている方向
    m[a][b] = 1;
    b += 1;
    m[a][b] = 2;
    a -= 1;
    dir = 1;
    for(int i = 3;i <= 1000000;i++){
        m[a][b] = i;
        if(dir == 0){ //→
            if(m[a-1][b] != 0){
                b += 1;
            }else{
                a -= 1;
                dir = 1;
            }
        }else if(dir == 1){ // ↑
            if(m[a][b-1] != 0){
                a -= 1;
            }else{
                b -= 1;
                dir = 2;
            }
        }else if(dir == 2){ //←
            if(m[a+1][b] != 0){
                b -= 1;
            }else{
                a += 1;
                dir = 3;
            }
        }else{ //↓
            if(m[a][b+1] != 0){
                a += 1;
            }else{
                b += 1;
                dir = 0;
            }
        }
    }

    prime[1] = true;
    for(int i = 2;i <= 1000000;i++){ //エラトス
        if(prime[i] == false){
            for(int j = 2;i*j <= 1000000;j++){
                prime[i*j] = true;
            }
        }
    }
    int mm,n;
    while(true){
        cin >> mm >> n;
        if(mm == 0 && n == 0)break;
        for(int i = 0;i < 1500;i++){
            for(int j = 0;j < 1500;j++){
                dp[i][j][0] = 0;
                dp[i][j][1] = 0;
                if(m[i][j] == n){
                    a = i;
                    b = j;
                }
            }
        }
        //cout << "a:" << a << ",b:" << b << endl;
        int aans = 0,bans = 0;
        if(prime[n] == false){
            dp[a][b][0] = 1;
            dp[a][b][1] = n;
            aans = 1;
            bans = n;
        }
        for(int i = a+1;i < 1500;i++){
            for(int j = b-(i-a);j <= b+(i-a);j++){
                if(m[i][j] == 0 || m[i][j] > mm)continue;
                int amax = 0,bmax = 0;
                for(int k = -1;k <= 1;k++){
                    if(amax < dp[i-1][j+k][0]){
                        amax = dp[i-1][j+k][0];
                        bmax = dp[i-1][j+k][1];
                    }else if(amax == dp[i-1][j+k][0] && bmax < dp[i-1][j+k][1]){
                        bmax = dp[i-1][j+k][1];
                    }
                }
                if(prime[m[i][j]] == false){
                    amax++;
                    bmax = m[i][j];
                }
                dp[i][j][0] = amax;
                dp[i][j][1] = bmax;
                if(aans < amax){
                    aans = amax;
                    bans = bmax;
                }else if(aans == amax && bans < bmax){
                    bans = bmax;
                }
            }
        }
        cout << aans << " " << bans << endl;
    }


}