Hints → https://atcoder.jp/contests/arc149/editorial/4961

[1] Using parity

Let us use the fact that any even number \(4\) or greater is not prime. Specifically, let us fill the upper half of the grid with odd numbers and the lower half with even numbers. Two different positive odd numbers, or two different positive even numbers, sum to an even number \(4\) or greater, which is not prime. Thus, almost all sums of two adjacent numbers in this grid are guaranteed not to be prime.

It remains to think of a way to do with the part where odd and even numbers are adjacent.

[2] Using multiples of \(3\)

Under the policy in [1], we just need to make around \(N\) pairs of odd and even numbers that do not sum to a prime number, and place them around the border of odd and even to achieve the objective.

This is a rather loose condition, which can be met in many ways. Here, let us do it by making the sums multiples of \(3\) that are \(6\) or greater.

When \(N\geq 6\), there are not less than \(N\) odd numbers and \(N\) even numbers that are multiples of \(3\). Let us place them around the border.

One simple way to implement it is to place the following from top to bottom in order.

• The odd numbers that are not multiples of \(3\)
• The odd numbers that are multiples of \(3\)
• The even numbers that are multiples of \(3\)
• The even numbers that are not multiples of \(3\)

This method of filling the border with multiples of \(3\) cannot handle the case \(3\leq N\leq 5\). There are only three instances, so it is reasonable to solve them by hand and hardcode the solutions, which look like the following.

For \(N=4\), one could use the Sample Output.

Sample solution

https://atcoder.jp/contests/arc149/submissions/35220957