打表程序(暴力)不知道为啥错了,找人帮忙。
#include<bits/stdc++.h>
using namespace std;
long long prime[1001],zhi[1001],num,l[1001],k[1001][1001],ans,anss[1001][1001],minn=100000000,m,t;
void dfs(long long x,long long y,long long n)
{
if(x>n)
{
t=1;
int ans=0;
for(int i=1;i<=n;i++) ans=ans+k[i][1]+k[1][i];//计算第一行第一列的和
ans=ans-k[1][1];
if(ans<minn)//更新答案
{
minn=ans;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){anss[i][j]=k[i][j];};
}
return;
}
for(int i=2;i<=n*n;i++)
{
if(l[i]==1) continue;//被用过的数跳过
if(l[i]==0)
{
if(x==1&&y==1)//好像不需要
{
k[x][y]=i;
l[i]=1;
if(y==n) dfs(x+1,1,n);
else dfs(x,1+y,n);
l[i]=0;
k[x][y]=0;
}
if(x==1&&y!=1)//最左边的格子只收到上面的数影响
{
if(prime[i+k[x][y-1]]==0)
{
k[x][y]=i;
l[i]=1;
if(y==n)dfs(x+1,1,n);
else dfs(x,y+1,n);
l[i]=0;
k[x][y]=0;
}
}
if(x!=1&&y==1)//最上面的只受左面的影响
{
if(prime[i+k[x-1][y]]==0)
{
k[x][y]==i;
l[i]=1;
if(y==n) dfs(x+1,1,n);
else dfs(x,y+1,n);
l[i]=0;
k[x][y]=0;
}
}
if(x!=1&&y!=1)//受到上面和左面的影响
{
if(prime[i+k[x-1][y]]==0&&prime[i+k[x][y-1]]==0)
{
k[x][y]==i;
l[i]=1;
if(y==n) dfs(x+1,1,n);
else dfs(x,y+1,n);
l[i]=0;
k[x][y]=0;
}
}
}
}
return ;
}
int main()
{
int n;
cin>>m;
prime[1]=1;
for(int i=2;i<=1001;i++)//zhi[i]表示第i个质数为zhi[i],prime[i]用于判断i是否为质数 ,0代表是,1代表不是
{
if(prime[i]==0)
{
num++;
zhi[num]=i;
}
for(int j=1;j<=num&&i*zhi[j]<=1001;j++)
{
prime[i*zhi[j]]=1;
if(i%zhi[j]==0) break;
}
}
// for(int i=1;i<=num;i++) cout<<prime[i]<<" ";线性筛
k[1][1]=1;//左上角为1
l[1]=1;
dfs(1,2,m);
if(t==0) cout<<"NO";//输出
else
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cout<<anss[i][j]<<" ";
}
cout<<endl;
}
}
}