No Prime Differences (Codeforces 1838C)
Tags: Math, number theory

You are given integers $$$n$$$ and $$$m$$$. Fill an $$$n$$$ by $$$m$$$ grid with the integers $$$1$$$ through $$$n\cdot m$$$, in such a way that for any two adjacent cells in the grid, the absolute difference of the values in those cells is not a prime number. Two cells in the grid are considered adjacent if they share a side.  It can be shown that under the given constraints, there is always a solution.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$4 \le n, m \le 1000$$$) — the dimensions of the grid.It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output $$$n$$$ lines of $$$m$$$ integers each, representing the final grid. Every number from $$$1$$$ to $$$n\cdot m$$$ should appear exactly once in the grid.The extra spaces and blank lines in the sample output below are only present to make the output easier to read, and are not required.If there are multiple solutions, print any of them.

Note: The first sample case corresponds to the picture above. The only absolute differences between adjacent elements in this grid are $$$1$$$, $$$4$$$, $$$6$$$, $$$8$$$, and $$$9$$$, none of which are prime. 

Sample Inputs:
3
4 4
5 7
6 4

Sample Outputs:
16  7  1  9
12  8  2  3
13  4 10 11
14  5  6 15

29 23 17  9  5  6  2
33 27 21 15 11  7  1
32 31 25 19 20 16 10
26 30 24 18 14  8  4
35 34 28 22 13 12  3

 2  3  7 11
 8  9  1 10
17 13  5  4
18 14  6 12
19 23 15 21
20 24 16 22

Solution (Python):
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
import fileinput
sys.setrecursionlimit(100000000)
data = fileinput.input()
inp = lambda : int(data.readline())
strng = lambda : data.readline().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(data.readline().strip())
mul = lambda : map(int, data.readline().strip().split())
mulf = lambda : map(float, data.readline().strip().split())
seq = lambda : list(map(int, data.readline().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def is_prime(n):
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
t = inp()
for _ in range(t):
    (n, m) = seq()
    M = [[0] * m for _ in range(n)]
    (p_n, p_m) = (is_prime(n), is_prime(m))
    if p_n and p_m:
        count = 1
        for i in range(0, n, 2):
            for j in range(m):
                M[i][j] = count
                count += 1
        for i in range(1, n, 2):
            for j in range(m):
                M[i][j] = count
                count += 1
    if p_n and (not p_m):
        count = 1
        for i in range(n):
            for j in range(m):
                M[i][j] = count
                count += 1
    if p_m and (not p_n):
        count = 1
        for i in range(m):
            for j in range(n):
                M[j][i] = count
                count += 1
    if not p_n and (not p_m):
        count = 1
        for i in range(n):
            for j in range(m):
                M[i][j] = count
                count += 1
    print(jn('', [jn(' ', i) + '\n' for i in M]))

Solution (Python):
(total_test_cases, output_list) = (int(input()), [])
for i in range(total_test_cases):
    (rows, columns) = list(map(int, input().split()))
    output_list.append('\n'.join(list((' '.join(list((str(columns * row + column + 1) if columns % 2 == 0 else str(columns * row + (row + column) % columns + 1) for column in range(columns)))) for row in range(rows)))))
print('\n\n'.join(output_list))

Solution (Python):
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
import fileinput
sys.setrecursionlimit(100000000)
data = fileinput.input()
inp = lambda : int(data.readline())
strng = lambda : data.readline().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(data.readline().strip())
mul = lambda : map(int, data.readline().strip().split())
mulf = lambda : map(float, data.readline().strip().split())
seq = lambda : list(map(int, data.readline().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def is_prime(n):
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
t = inp()
for _ in range(t):
    (n, m) = seq()
    M = [[0] * m for _ in range(n)]
    count = 1
    for i in range(1, n, 2):
        for j in range(m):
            M[i][j] = count
            count += 1
    for i in range(0, n, 2):
        for j in range(m):
            M[i][j] = count
            count += 1
    print(jn('', [jn(' ', i) + '\n' for i in M]))