解题思路

题目要我们做两件事：

第一步：生成前 n×n 个素数。

用埃氏筛：先假设 2 到某个范围里的所有数都是素数，然后从 2 开始，把 2 的倍数划掉，再把 3 的倍数划掉，把 5 的倍数划掉……剩下的就是素数。

因为不知道具体要筛到多大，我们可以先定一个小范围，如果筛出来的素数个数不够 n×n，就把范围加倍再筛一次，直到够为止。这样可以保证任何 n 都不会出错。

第二步：把素数按“右、下、左、上……”螺旋填入方阵。

从左上角开始，用变量 top、bottom、left、right 记录四个边界，用 dir 记录当前方向。每填一个数，就走一步：

• 往右走，碰到右边界就转向下，同时上边界往里缩一行；
• 往下走，碰到底边界就转向左，同时右边界往里缩一列；
• 往左走，碰到左边界就转向上，同时下边界往里缩一行；
• 往上走，碰到上边界就转向右，同时左边界往里缩一列。

这样一圈圈往内走，正好把所有 n×n 个格子填满。最后输出第 x 行第 y 列的数即可。

参考代码

// P4487 蛇形素数矩阵：把前n*n个素数按"右、下、左、上"螺旋填入方阵，输出第x行第y列
#include <iostream>
using namespace std;

int a[1005][1005];   // 蛇形素数方阵

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    int need = n * n;          // 需要的素数个数

    // 用埃氏筛生成素数。先定一个筛的范围，素数不够就把范围加倍重筛
    int limit = 2;             // 当前筛的范围
    char* isp = NULL;          // isp[i]==1 表示 i 是素数
    while (true) {
        if (isp) delete[] isp;
        isp = new char[limit + 1];
        for (int i = 0; i <= limit; i++) isp[i] = 1;
        isp[0] = isp[1] = 0;   // 0 和 1 不是素数
        for (int i = 2; i * i <= limit; i++)
            if (isp[i])                    // i 是素数，就把 i 的倍数都划掉
                for (int j = i * i; j <= limit; j += i) isp[j] = 0;
        int cnt = 0;                       // 统计范围内的素数个数
        for (int i = 2; i <= limit; i++) if (isp[i]) cnt++;
        if (cnt >= need) break;            // 素数够了，停止
        limit *= 2;                        // 不够就把范围扩大一倍再筛
    }
    int* prime = new int[need];            // 按从小到大收集需要的素数
    int cnt = 0;
    for (int i = 2; i <= limit && cnt < need; i++)
        if (isp[i]) prime[cnt++] = i;

    // 从左上角开始，按 右、下、左、上…… 的顺序螺旋填入
    int r = 1, c = 1;      // 当前位置（1表示第1行第1列）
    int top = 1, bottom = n, left = 1, right = n;  // 四个边界
    int dir = 0;           // 0右 1下 2左 3上
    for (int k = 0; k < need; k++) {
        a[r][c] = prime[k];          // 填入第 k+1 个素数
        // 判断下一步往哪里走：走到边界就转方向，并收缩对应边界
        if (dir == 0) {              // 向右走
            if (c == right) { dir = 1; top++; r++; }   // 到右边界：转向下
            else c++;
        } else if (dir == 1) {       // 向下走
            if (r == bottom) { dir = 2; right--; c--; }  // 到下边界：转向左
            else r++;
        } else if (dir == 2) {       // 向左走
            if (c == left) { dir = 3; bottom--; r--; }   // 到左边界：转向上
            else c--;
        } else {                     // 向上走
            if (r == top) { dir = 0; left++; c++; }      // 到上边界：转向右
            else r--;
        }
    }
    cout << a[x][y] << endl;   // 输出第x行第y列的数值
    delete[] isp;
    delete[] prime;
    return 0;
}

复杂度分析

埃氏筛的时间约为 O(L·log log L)（L 是筛的上界，和 n² 同阶）；螺旋填 n×n 个格子是 O(n²)。空间上存方阵和素数表，约为 O(n²)。