记录编号	604786	评测结果	AAAAAAAAAA
题目名称	101.填数	最终得分	100
用户昵称	梧叶已同秋雨去	是否通过	通过
代码语言	C++	运行时间	0.531 s
提交时间	2025-08-11 19:47:23	内存使用	3.68 MiB

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