提出 #35353475

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

const int mxn = 1000 + 5, mxp = 2 * 1000 * 1000 + 5;

using BS = bitset <mxp>;

bool isp[mxp];
BS notp;

int main()
{
	ios::sync_with_stdio(0);
	for (int i = 2; i < mxp; ++ i) isp[i] = 1;
	for (int i = 2; i * i < mxp; ++ i) if (isp[i])
		for (int j = i * i; j < mxp; j += i) isp[j] = 0;
	for (int i = 2; i < mxp; ++ i) if (!isp[i]) notp.set(i);
	int n;
	cin >> n;
	vector <int> v_even;
	for (int i = 2; i <= n * n; i += 2) v_even.push_back(i);
	while (true)
	{
		random_shuffle(v_even.begin(), v_even.end());
		int zz = -1;
		if (n % 2 == 1)
		{
			if (n == 3) zz = 7;
			else zz = n * n;
		}
		static BS full;
		for (int i = 1; i <= n * n; i += 2) if (i != zz) full.set(i);
		vector <pair <int, int> > chose;
		for (int i : v_even)
		{
			static BS temp;
			temp = full & (notp >> i);
			if (temp.any())
			{
				int x = rand() % temp.count();
				int j = temp._Find_first();
				while (x --) j = temp._Find_next(j);
				chose.push_back({i, j});
				full.reset(j);
				if ((int) chose.size() >= n / 2 * 2) break;
			}
		}
		if ((int) chose.size() >= n / 2 * 2)
		{
			if (n % 2 == 1)
			{
				int hav = -1;
				for (int i = 0; i < (int) chose.size(); ++ i)
					if (!isp[chose[i].first + zz])
					{
						hav = i;
						break;
					}
				if (!~hav) continue;
				static bool vis[mxp];
				for (int i = 1; i <= n * n; ++ i) vis[i] = 0;
				for (int i = 0; i < (int) chose.size(); ++ i) vis[chose[i].first] = vis[chose[i].second] = 1;
				int hav1 = -1;
				for (int i = 2; i < n * n; i += 2) if (!vis[i] && !isp[i + zz])
				{
					hav1 = i;
					break;
				}
				if (!~hav1) continue;
				swap(chose[hav], chose[n / 2 - 1]);
				vis[hav1] = 1;
				static int mat[mxn][mxn];
				mat[n / 2][n / 2] = zz;
				mat[n / 2][n / 2 + 1] = hav1;
				for (int i = 0; i < n / 2; ++ i)
				{
					mat[i][n / 2 - 1] = chose[i].second;
					mat[i][n / 2] = chose[i].first;
				}
				for (int i = n / 2 + 1; i < n; ++ i)
				{
					mat[i][n / 2] = chose[i - 1].second;
					mat[i][n / 2 + 1] = chose[i - 1].first;
				}
				vis[zz] = 1;
				int ptr = 1;
				for (int i = 0; i < n; ++ i)
					for (int j = 0; j < n / 2; ++ j) if (!mat[i][j])
					{
						while (vis[ptr]) ptr += 2;
						mat[i][j] = ptr;
						vis[ptr] = 1;
					}
				ptr = 2;
				for (int i = 0; i < n; ++ i)
					for (int j = n / 2 + 1; j < n; ++ j) if (!mat[i][j])
					{
						while (vis[ptr]) ptr += 2;
						mat[i][j] = ptr;
						vis[ptr] = 1;
					}
				for (int i = 0; i < n; ++ i)
					for (int j = 0; j < n; ++ j)
					{
						if (i + 1 < n) assert(!isp[mat[i][j] + mat[i + 1][j]]);
						if (j + 1 < n) assert(!isp[mat[i][j] + mat[i][j + 1]]);
					}
				for (int i = 0; i < n; ++ i)
					for (int j = 0; j < n; ++ j)
						cout << mat[i][j] << " \n"[j + 1 == n];
				return 0;
			} else
			{
				static bool vis[mxp];
				static int mat[mxn][mxn];
				for (int i = 0; i < (int) chose.size(); ++ i)
				{
//					cerr << "	" << chose[i].first << " " << chose[i].second << endl;
					vis[chose[i].first] = vis[chose[i].second] = 1;
					mat[n / 2 - 1][i] = chose[i].first;
					mat[n / 2][i] = chose[i].second;
				}
				int ptr = 2;
				for (int x = 0; x < n / 2 - 1; ++ x)
					for (int y = 0; y < n; ++ y)
					{
						while (vis[ptr]) ptr += 2;
						mat[x][y] = ptr;
						vis[ptr] = 1;
					}
				ptr = 1;
				for (int x = n / 2 + 1; x < n; ++ x)
					for (int y = 0; y < n; ++ y)
					{
						while (vis[ptr]) ptr += 2;
						mat[x][y] = ptr;
						vis[ptr] = 1;
					}
				for (int i = 0; i < n; ++ i)
					for (int j = 0; j < n; ++ j)
					{
						if (i + 1 < n) assert(!isp[mat[i][j] + mat[i + 1][j]]);
						if (j + 1 < n) assert(!isp[mat[i][j] + mat[i][j + 1]]);
					}
				for (int i = 0; i < n; ++ i)
					for (int j = 0; j < n; ++ j)
						cout << mat[i][j] << " \n"[j + 1 == n];
				return 0;
			}
		}
	}
	return 0;
}

提出情報

ジャッジ結果