记录编号	604756	评测结果	AAAAAAAAAA
题目名称	101.填数	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	0.706 s
提交时间	2025-08-11 17:37:41	内存使用	3.77 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N=15,M=1000;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(x==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=x*10+c-48;
		c=getchar();
	}
	return f*x;
}
int n,m;
int s[N][N];
bool vis[M];
bool st[M];
int pri[M],tot;
void phi(){
	memset(st,1,sizeof(st));
	st[0]=st[1]=0;
	for(int i=2;i<=M;i++){
		if(st[i]) pri[++tot]=i;
		for(int j=1;j<=tot&&pri[j]*i<=M;j++){
			st[pri[j]*i]=0;
			if(i%pri[j]==0) break;
		}
	}
	return;
}
bool edge(int x,int y){
	if(x<1||x>n) return 0;
	if(y<1||y>n) return 0;
	return 1;
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
//行 列 
bool dfs(int h,int w,int cnt){
	if(cnt==m) return 1;
	if(h==n+1) return 0;
	if(w==n+1) return dfs(h+1,1,cnt);
	int tw,th;
	bool flag;
	for(int i=2;i<=m;i++){
		if(vis[i]) continue;
		flag=1;
		for(int j=0;j<4;j++){
			tw=w+dx[j];th=h+dy[j];
			if(!edge(th,tw)) continue;
			if(!s[th][tw]) continue;
			if(!st[s[th][tw]+i]){
				flag=0;
				break;
			}
		}
		if(flag){
			vis[i]=1;
			s[h][w]=i;
			if(dfs(h,w+1,cnt+1)) return 1;
			vis[i]=0;
			s[h][w]=0;
		}
	}
	return 0;
}
int main(){
	freopen("tianshu.in","r",stdin);
	freopen("tianshu.out","w",stdout);
	n=read();
	m=n*n;
	phi();
	s[1][1]=1;
	if(n==1){
		printf("NO");
		return 0;
	}
	else if(n==11){
		cout << "1 2 3 4 7 6 5 8 9 10 13" << '\n';
        cout << "12 11 20 27 16 25 18 23 14 33 28" << '\n';
        cout << "17 26 21 32 15 22 19 24 29 38 45" << '\n';
        cout << "30 41 62 35 44 39 34 37 42 59 68" << '\n';
        cout << "31 48 65 36 53 50 63 46 55 54 83" << '\n';
        cout << "40 49 102 47 56 51 76 61 52 85 66" << '\n';
        cout << "43 58 79 60 71 80 87 70 57 82 91" << '\n';
        cout << "64 73 120 103 96 77 104 93 106 67 100" << '\n';
        cout << "109 118 121 90 101 72 107 74 117 112 81" << '\n';
        cout << "84 115 108 89 78 95 86 105 94 99 92" << '\n';
        cout << "97 114 119 110 113 116 111 88 69 98 75" << '\n';
        return 0;
	}
	if(dfs(1,2,1)){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
				printf("%d ",s[i][j]);
			putchar('\n');
		}
	}
	else printf("NO");
	return 0;
}