我终于不再是没有马丽的人了

在此给出一个跑的飞快的总耗时为90ms的做法 首先不难注意到一个性质： 末尾一行和末尾一列这两个数一定是每一位为非 $5$ 奇数的数。原因请读者自己思考。

然后不难发现像这样的质数只有249个！ 那很好了，完全可以先把这些质数打成表，优先去填这些数。

填好后，我们来看下图 其中，红色的部分是我们已经填好的，不难注意到上面四条绿线都是头尾填好的，那么我们自然可以预处理出以任意数字开头任意数字结尾的质数，将它们放到一个三维数组中。

所以第二步是填对角线和四周。

填好后，整个方阵就只剩下了四个位置 那好办啊，它们都可以通过用k减另外四个数得到，填上之后再check就好了

总结一下，我们填的顺序就是这样:

于是你就可以得到一个跑的飞快的check矩阵以便调试代码的代码：

#include<iostream>
#include<cmath>
using namespace std;
const int N=1e7+10;
int prime[N],vis[N];
int tot;
void EulerPrime(){
	for(int i=2;i<=N;i++){
		if(!vis[i])prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int a[10][10];
signed main(){
	EulerPrime();
	while(1){
		for(int i=1;i<=5;i++){
			for(int j=1;j<=5;j++){
				char c;
				cin>>c;
				a[i][j]=c-'0';
			}
		}
		cout<<"5 行："<<endl;
		for(int i=1;i<=5;i++){
			int sum=0;
			for(int j=1;j<=5;j++)sum+=a[i][j];
			cout<<sum<<endl;
		}
		cout<<endl;
		cout<<"5 列："<<endl;
		for(int i=1;i<=5;i++){
			int sum=0;
			for(int j=1;j<=5;j++)sum+=a[j][i];
			cout<<sum<<endl;
		}
		cout<<endl;
		
		cout<<"对角线："<<endl;
		int sum=0;
		for(int i=1;i<=5;i++)sum+=a[i][i];
		cout<<sum<<endl;
		sum=0;
		for(int i=1;i<=5;i++)sum+=a[6-i][i];
		cout<<sum<<endl;
		cout<<endl;
		
		for(int i=1;i<=5;i++){
			sum=0;
			for(int j=1;j<=5;j++){
				sum+=a[i][j]*pow(10,5-j);
			}
			if(!vis[sum])cout<<sum<<" is prime"<<endl;
			else cout<<sum<<" is not prime"<<endl;
		}
		cout<<endl;
		for(int i=1;i<=5;i++){
			sum=0;
			for(int j=1;j<=5;j++){
				sum+=a[j][i]*pow(10,5-j);
			}
			if(!vis[sum])cout<<sum<<" is prime"<<endl;
			else cout<<sum<<" is not prime"<<endl;
		}
		cout<<endl;
		sum=0;
		for(int i=1;i<=5;i++)sum+=a[i][i]*pow(10,5-i);
		if(!vis[sum])cout<<sum<<" is prime"<<endl;
		else cout<<sum<<" is not prime"<<endl;
		cout<<endl;
		sum=0;
		for(int i=1;i<=5;i++)sum+=a[6-i][i]*pow(10,5-i);
		if(!vis[sum])cout<<sum<<" is prime"<<endl;
		else cout<<sum<<" is not prime"<<endl;
		cout<<endl;		
	}
	return 0;
}

真正的代码：

深度优先搜索，电风扇。

按照序顺索搜12345678910号

ai表示第i行的前缀，bi表示第i的前缀，c，d分别表示对角线的前缀。

然后把满足条件的数按照前缀存到vector里面，vec[i]表示数字前缀为i的所有满足条件的数。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int k,x,ok[N],cnt,getnum[N][6],flag,npr[N];
vector<int>vec[100005];
string ANS[10005];int an;

int ans[15],a[15],b[15],c,d;
void dfs(int u);

void vec_(int l,int r,int f);

signed main() {
	cin>>k>>x;
	for(int i=2; i<=99999; ++i) {
		if(npr[i])continue;
		for(int j=i; j<=99999/i; ++j) {
			npr[i*j]=1;
		}
	}
	for(int i=10000; i<=99999; ++i) {
		if(npr[i])continue;
		int t=i,j=0;
		while(t) {
			j+=t%10;
			t/=10;
		}
		if(j==k) {
			ok[++cnt]=i;
			t=i,j=5;
			while(t) {
				getnum[i][j--]=t%10,t/=10;
			}
		}
	}
	vec_(1,9,10000),vec_(10,99,1000);
	vec_(100,999,100),vec_(1000,9999,10);
	vec_(10000,99999,1);
	for(int i=0,v; i<vec[x].size(); ++i) {
		v=vec[x][i];
		flag=1;
		for(int j=1; j<=5; ++j) {
			if(!getnum[v][j]) {
				flag=0;
				break;
			}
			b[j]=getnum[v][j];
			a[j]=0;
		}
		if(flag) {
			c=getnum[v][1];
			d=0;
			ans[1]=v;
			dfs(2);
		}
	}
	sort(ANS+1,ANS+1+an);
	for(int i=1;i<=an;++i){
		cout<<ANS[i][0]<<ANS[i][1]<<ANS[i][2]<<ANS[i][3]<<ANS[i][4]<<"\n";
		cout<<ANS[i][5]<<ANS[i][6]<<ANS[i][7]<<ANS[i][8]<<ANS[i][9]<<"\n";
		cout<<ANS[i][10]<<ANS[i][11]<<ANS[i][12]<<ANS[i][13]<<ANS[i][14]<<"\n";
		cout<<ANS[i][15]<<ANS[i][16]<<ANS[i][17]<<ANS[i][18]<<ANS[i][19]<<"\n";
		cout<<ANS[i][20]<<ANS[i][21]<<ANS[i][22]<<ANS[i][23]<<ANS[i][24]<<"\n\n";
	}
	return 0;
}
void dfs(int u) {
	if(u==11) {
		++an;
		int pos=0;
		for(int i=1; i<=10; i+=2) {
			for(int j=1;j<=5;++j){
				ANS[an]+=getnum[ans[i]][j]+'0'; 
			}
		}
		return ;
	}
	if(u&1) {
		for(int i=0; i<vec[a[u/2+1]].size(); ++i) {
			int v=vec[a[u/2+1]][i];
			flag=1;
			for(int j=u/2+1; j<=5; ++j) {
				if(!vec[b[j]*10+getnum[v][j]].size()) {
					flag=0;
					break;
				}
			}
			if(!vec[c*10+getnum[v][u/2+1]].size()) {
				flag=0;
			}
			if(flag) {
				for(int j=u/2+1; j<=5; ++j) {
					b[j]=b[j]*10+getnum[v][j];
				}
				c=c*10+getnum[v][u/2+1];
				ans[u]=v;
				dfs(u+1);
				for(int j=u/2+1; j<=5; ++j) {
					b[j]=(b[j]-getnum[v][j])/10;
				}
				c=(c-getnum[v][u/2+1])/10;
				ans[u]=0;
			}
		}
	} else {
		for(int i=0; i<vec[b[u/2]].size(); ++i) {
			int v=vec[b[u/2]][i];
			flag=1;
			for(int j=u/2+1; j<=5; ++j) {
				if(u==2&&getnum[v][j]==0) {
					flag=0;
					break;
				}
				if(!vec[a[j]*10+getnum[v][j]].size()) {
					flag=0;
					break;
				}
			}
			if(!vec[d*10+getnum[v][6-u/2]].size()) {
				flag=0;
			}
			if(flag) {
				for(int j=u/2+1; j<=5; ++j) {
					a[j]=a[j]*10+getnum[v][j];
				}
				d=d*10+getnum[v][6-u/2];
				ans[u]=v;
				dfs(u+1);
				for(int j=u/2+1; j<=5; ++j) {
					a[j]=(a[j]-getnum[v][j])/10;
				}
				d=(d-getnum[v][6-u/2])/10;
				ans[u]=0;
			}
		}
	}
}
void vec_(int l,int r,int f) {
	for(int i=l; i<=r; ++i) {
		for(int j=1; j<=cnt; ++j) {
			if(ok[j]/f==i) {
				vec[i].push_back(ok[j]);
			}
		}
	}
}