gistfile2.txt

wrong.cpp

#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("prime3.in");
ofstream fout("prime3.out");

int square[5][5];
int primetable[10][10][10][10][10];//big to small

int sum;

bool IsPrime(int n)
{
	int r = sqrt((double)n);
	for (int i = 2; i<=r;i++)
	{
		if (n%i==0)
		{
			return false;
		}
	}
	return true;
}

int nprime;
void generate_primetable()
{
	int a[5];
	for (int i = 10000; i<100000; i++)
	{
		int tsum = 0;
		int temp = i;
		if (temp%2==0)
		{
			continue;
		}
		while (temp)
		{
			tsum += temp%10;
			temp/=10;
		}
		if (tsum!=sum)
		{
			continue;
		}
		if (IsPrime(i))
		{
			int indes = 0;
			memset(a,0,5);
			int temp = i;
			while (temp)
			{
				a[indes++] = temp%10;
				temp /= 10;
			}
			primetable[a[4]][a[3]][a[2]][a[1]][a[0]] = 1;
			nprime++;
		}
	}
}

//int res[500][5];//hard to sort
struct NODE{int a[5];}res[600];//big to small
int nres;
void fprocess()
{
	for (int i = 0 ; i<5 ;i++)
	{
		for (int j = 0 ; j<5; j++)
		{
			res[nres].a[i] += square[i][j]*10000/pow(10,(double)j);
		}
	}
	nres++;
}
void row3(int k)
{
	if (square[3][0]==0&&k!=0)
	{
		return;
	}

	if (k==1)
	{
		square[3][4] = sum -square[3][0]-square[3][1] -square[3][2]-square[3][3];
		if (square[3][4]<0||square[3][4]>9)
		{
			return;
		}
		if (!primetable[square[3][0]][square[3][1]][square[3][2]][square[3][3]][square[3][4]])
		{
			return;
		}
		square[2][0] = sum - square[0][0]-square[1][0]-square[3][0]-square[4][0];
		square[2][4] = sum - square[0][4]-square[1][4]-square[3][4]-square[4][4];
		if (square[2][0]<0||square[2][0]>9)
		{
			return;
		}
		if (square[2][4]<0||square[2][4]>9)
		{
			return;
		}
		if (!primetable[square[2][0]][square[2][1]][square[2][2]][square[2][3]][square[2][4]])
		{
			return;
		}
		if (!primetable[square[0][0]][square[1][0]][square[2][0]][square[3][0]][square[4][0]])
		{
			return;
		}
		if (!primetable[square[0][4]][square[1][4]][square[2][4]][square[3][4]][square[4][4]])
		{
			return;
		}
		//finalprocess 
		fprocess();
		return;
	}
	for (int i = 0; i<10; i++)
	{
		square[3][k] = i;
		row3(k+1);
	}

}
void row1(int k)
{

	if (square[1][0]==0&&k!=0)
	{
		return;
	}
	if (k==1)
	{
		square[1][4] = sum -square[1][0]-square[1][1] -square[1][2]-square[1][3];//
		if (square[1][4]<0||square[1][4]>9)
		{
			return;
		}
		if (!primetable[square[1][0]][square[1][1]][square[1][2]][square[1][3]][square[1][4]])
		{
			return;
		}
		row3(0);//?
		return;
	}
	for (int i = 0; i<10; i++)
	{
		square[1][k] = i;
		row1(k+1);
	}

}
void row4(int k)
{

	if (k==2)
	{
		square[4][3] = sum -square[4][0] -square[4][1]-square[4][2]-square[4][4];
		if (square[4][3]<0||square[4][3]>9)
		{
			return;
		}
		if (!primetable[square[4][0]][square[4][1]][square[4][2]][square[4][3]][square[4][4]])
		{
			return;
		}
		square[2][1] = sum -square[0][1] -square[1][1]-square[3][1]-square[4][1];
		if (square[2][1]<0||square[2][1]>9)
		{
			return;
		}
		if (!primetable[square[0][1]][square[1][1]][square[2][1]][square[3][1]][square[4][1]])
		{
			return;
		}
		square[2][3] = sum -square[0][3] -square[1][3]-square[3][3]-square[4][3];
		if (square[2][3]<0||square[2][3]>9)
		{
			return;
		}
		if (!primetable[square[0][3]][square[1][3]][square[2][3]][square[3][3]][square[4][3]])
		{
			return;
		}
		row1(0);
		return;
	}
	for (int i = 0; i<10; i++)
	{
		square[4][k] = i;
		row4(k+1);
	}

}
void row0(int k)
{

	if (k==2)
	{
		square[0][3] = sum -square[0][0] -square[0][1]-square[0][2]-square[0][4];
		if (square[0][3]<0||square[0][3]>9)
		{
			return;
		}
		if (!primetable[square[0][0]][square[0][1]][square[0][2]][square[0][3]][square[0][4]])
		{
			return;
		}
		row4(1);//?
		return;
	}
	for (int i = 1; i<10; i++)
	{
		square[0][k] = i;
		row0(k+1);
	}

}
void col2(int k)
{
	int sum1 = 0;
	for (int i = 0; i<k; i++)
	{
		sum1 += square[i][2];
	}
	if (sum1>sum||sum1==0&&k!=0||sum1!=sum&&k==5)
	{
		return;
	}
	if (k==5)
	{
		if (!primetable[square[0][2]][square[1][2]][square[2][2]][square[3][2]][square[4][2]])
		{
			return;
		}
		row0(1);//?
		return;
	}
	for (int i = 0; i<10; i++)
	{
		if (k==4&&i%2==0)
		{
			continue;
		}
		if (k==0&&i==0)
		{
			continue;
		}
		if (k!=2)
			square[k][2] = i;
		col2(k+1);
	}

}


void diag2(int k)
{
	int sum1 = 0;
	for (int i = 0; i<k; i++)
	{
		sum1 += square[4-i][i];
	}
	if (sum1>sum||sum1==0&&k!=0||sum1!=sum&&k==5)
	{
		return;
	}
	if (k==5)
	{
		if (!primetable[square[4][0]][square[3][1]][square[2][2]][square[1][3]][square[0][4]])
		{
			return;
		}
		col2(0);//?
		return;
	}
	for (int i = 0; i<10; i++)
	{
		if (k==4&&i%2==0)
		{
			continue;
		}
		if (k==0&&i==0)
		{
			continue;
		}
		if (k!=2)
			square[4-k][k] = i;
		diag2(k+1);
		
	}

}
void diag1(int k)
{
	int sum1 = 0;
	for (int i = 0; i<k; i++)
	{
		sum1 += square[i][i];
	}
	if (sum1>sum||sum1!=sum&&k==5)
	{
		return;
	}
	if (k==5)
	{
		if (!primetable[square[0][0]][square[1][1]][square[2][2]][square[3][3]][square[4][4]])
		{
			return;
		}
		diag2(0);
		return;
	}
	for (int i = 0; i<10; i++)
	{
		if (k==4&&i%2==0)
		{
			continue;
		}
		square[k][k] = i;
		diag1(k+1);
	}
	
}

bool cmp( NODE p , NODE q )
{
	for (int i = 0 ; i<5 ;i++)
	{
		if (p.a[i]<q.a[i]) return true;
		else if (p.a[i]>q.a[i]) return false;
	}
	return true;
}

void output()
{
	if (!nres)
	{
		fout<<"NONE"<<endl;
		return;
	}
	for (int i = 0 ; i<nres ;i++)
	{
		for (int j = 0 ; j<5 ;j++)
		{
			int temp = res[i].a[j];
			int zerobit = 0;
			while (temp)
			{
				zerobit++;
				temp/=10;
			}
			zerobit = 5-zerobit;
			for (int i=0;i<zerobit;i++)
				fout<<'0';
			fout<<res[i].a[j]<<endl;
		}
		fout<<endl;
	}
}
int main()
{
	fin>>sum>>square[0][0];
	
	generate_primetable();
	
	//backtracking
	diag1(1);
	
	
	//sort
	//sort(res,res+nres,cmp);

	//output
	output();
	
	fin.close();
	fout.close();
	return 0;
}