记录编号	604776	评测结果	AAAAAAAAAA
题目名称	101.填数	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	0.526 s
提交时间	2025-08-11 19:26:24	内存使用	3.69 MiB

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

	}else{
		vis[1]=1,a[1][1]=1;
		dfs(1,2);
		printf("NO\n");
	}
	return 0;
}